Stern scales

I mentioned in Three gaps, part 1 an article I have about xenharmonic musical scales, and in that article I mention a link between two-gap scales (MOS scales, as they’re somewhat reluctantly called there) and something called Stern’s diatomic series. As discussed previously, if you generate scales using a generator equal to 1200\log_2 (3/2)\approx 702 cents, then you get two-gap scales with 2, 3, 5, 7, 12, 17… notes. Each of these numbers (starting with 5) is the sum of the immediately preceding number and one of the other preceding numbers:

5 = 3 + 2
7 = 5 + 2
12 = 7 + 5
17 = 12 + 5

and so on. Specifically each number is the sum of the immediately preceding one and one of the two numbers summed to make the immediately preceding one.

If you vary the generator by a small amount (and it’s still irrational) you get the same sequence to a point, and then it differs: for a musically significant example, a quarter comma tempered fifth, 1200\log_2 [(3/2)/(81/80)^{1/4}]\approx 697 cents, the sequence is 2, 3, 5, 7, 12, 19… . Notice that the two numbers summed to make 12 are 7 and 5, and the two numbers summed to make 17 are 12, the immediately preceding one, and 5 which is one of the numbers in the sum for 12, while the two numbers summed to make 19 are 12 and 7, the other number in the sum for 12. Of course the sequence terminates if the generator is rational: for a generator of 700 cents, for example, it goes 2, 3, 5, 7; then the 8- through 11-note scales are all two-gap, and the 12-note scale is one-gap, i.e., an equal division of the octave. It stops there because further applications of the generator just give back notes you already have.

A generator for a 17-note equal division is 1200\times10/17 = 705\ 15/17 cents and a generator for a 19-note equal division is 1200\times11/19 = 694\ 14/19 cents. Generators between these two values (other than 700 cents) will give 2, 3, 5, 7, and 12 note two-gap scales, with ones below 700 going on to 19 and ones above 700 going on to 17. Generators a little outside that range will not give 12-note scales; they’ll go 2, 3, 5, 7, 9… if below the range or 2, 3, 5, 8, 13… if above. A diagram from which one can read off the 2-gap scales for generators from 685 to 720 cents is here, and for all generators from 600 to 1200 cents is here (the diagram for 0 to 600 cents is just a mirror image).

Stare at the first of those diagrams and you see 47 appears in two places. That is, the 47-note equal division can be generated by two different generators in that range: 1200\times27/47\approx 689 cents and 1200\times28/47\approx 715 cents.

In fact, looking at the whole range from 0 to 1200 cents, there must be 46 generators for a 47-note equal division: 1200\times n/47 for n = 1..46. That’s because 47 is prime. For a 46-note equal division, though, 1200\times n/46 will generate the scale only for odd n; even values will generate only a 23-note scale. And in general, the generators for an m-note equal division are 1200\times n/m for values of n where 1\le n < m and n and m are relatively prime. The familiar 12-note equal division has only four generators: 1200\times 1/121200\times 5/121200\times 7/12, and 1200\times 11/12 cents.

Examine that diagram some more and you can see how it relates to a sequence of numbers developed as follows: Start with

5, 7

and interpolate the sum of the adjacent numbers

5, 12, 7

(in the diagram, 12 is linked to the horizontal lines associated with 5 and 7); and again

5, 17, 12, 19, 7

(17 is linked to 5 and 12, 19 to 12 and 7); and again

5, 22, 17, 29, 12, 31, 19, 26, 7

(22 is linked to 5 and 17, and so on); and again

5, 27, 22, 39, 17, 46, 29, 41, 12, 43, 31, 50, 19, 45, 26, 33, 7

ad infinitum. Those two values of 47 arise in later iterations of the this sequence from 27+5+5+5 and 33+7+7.

Likewise the big diagram and its mirror image relate to:

1, 1
1, 2, 1
1, 3, 2, 3, 1
1, 4, 3, 5, 2, 5, 3, 4, 1
1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1

et cetera. We can concatenate the rows of this, dropping the 1s from one end, into a single sequence:

1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, …

which we can define with the recurrence relation:

b(1) = 1
b(2n) = b(n)
b(2n+1) = b(n) + b(n+1)

This is known as Stern’s diatomic series, A002487 in OEIS.

From that definition it’s not at all obvious that, for instance, 47 will arise as a sum 46 times while 12 will arise as a sum only 4 times. It’s true though. In fact, consider the following sequence of rational numbers:

1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1…

That’s just each entry in Stern’s series divided by the subsequent entry. But there’s a theorem: The nth rational number, in reduced form, can be taken to be b(n)/b(n + 1), for n = 0, 1, 2 … That is, b(n) and b(n + 1) are relatively prime, and each positive reduced rational number occurs once and only once in the list b(0)/b(1), b(1)/b(2), … Or to put it another way, Stern’s series provides a way to enumerate the rational numbers.

The theorem’s proved in Calkin, N., & Wilf, H. (2000). Recounting the Rationals. The American Mathematical Monthly, 107(4), 360-363. doi:10.2307/2589182, if you want to look at it. Another fact about the series, also discussed there, is b(n) is the number of ways of writing the integer n as a sum of powers of 2, each power being used at most twice (i.e., once more than the legal limit for binary expansions).

Every positive integer appears in the list surrounded by two smaller numbers, which are relatively prime and sum to n, exactly once for each such possible distinct sum (counting m, n, n-m and n-m, n, m as distinct). So one finds 1, 12, 11; 5, 12, 7; 7, 12, 5; and 11, 12, 1; and no other instances of 12 adjacent to smaller numbers. On the other hand, one finds all 46 of 1, 47, 46; 2, 47, 45; 3, 47, 44; … 45, 47, 2; and 46, 47, 1.

Mind you, you have to look through a lot of numbers to find them. After all, 1 appears adjacent to n and n-1 at position 2^{n-1} in the series: 1 followed by 2 and 1 is at position 2, 1 then 3 and 2 at position 4, 1 then 4 and 3 at position 8, and so on. 1 followed by 47 and 46 appears at position 2^{46} = 70,368,744,177,664(!) So if you want to figure out how many numbers are smaller than and relatively prime to 47, examining Stern’s series may not be the best approach.

 

Advertisements

Riddlers for 4 May 2018

Spoilers for last week’s fivethirtyeight.com Riddler Express and Classic:

Express

From Charlie Drinnan, find the letters’ numbers:

If A, B, C, D and E are all unique digits, what values would work with the following equation?

ABC,CDE × 4 = EDC,CBA

No problem. A must be even, and 4A < 10, so A=2. Then 4AB < 100 so B < 5, and BA\mod 4 = 0 so B = 1 and E = 8, or B = 3 and E = 9. But 4E \mod 10 = A = 2 so E = 8.

Now 4D+3 \mod 10 = B = 1 so 4D \mod 10 = 8. D\ne 2 so D = 7.

Finally 4C+3 \mod 10 = C or 3C\mod 10 = 7, so C = 9.

219,978 \times 4= 879,912.

Classic

This is fairly mechanical although I tripped up several times on the way.

Let n_i be the number of coconuts found by the ith pirate, and n_8 be the number of coconuts found in the morning. n_8 is divisible by 7 so write n_8 = 7m_8.

But n_8 is what was left when the seventh pirate discarded one coconut out of n_7 and hid one seventh of the rest, so n_7 = (7/6)n_8+1 = (7/6)(7m_8)+1. For that to be an integer m_8 must be a multiple of 6, so write m_8 = 6m_7. Then n_7 = 7^2m_7+1.

Now n_6 = (7/6)n_7+1 = (7/6)(7^2m_7+1)+1. For integer value, 7^2m_7\mod 6 = m_7\mod 6 = 5, so write m_7 = 6m_6+5. Then n_6 = (7/6)(7^2(6m_6+5)+1)+1 = 7^3m_6+288.

You see how this goes.

n_5 = (7/6)n_6+1 = (7/6)(7^3m_6+288)+1. For integer value, m_6\mod 6 = 0, so write m_6 = 6m_5. Then n_5 = (7/6)(7^3(6m_5)+288))+1 = 7^4m_5+337.

n_4 = (7/6)n_5+1 = (7/6)(7^4m_5+337)+1. For integer value, m_5\mod 6 = 5, so write m_5 = 6m_4+5. Then n_4 = (7/6)(7^4(6m_4+5)+337)+1 = 7^5m_4+14400.

n_3 = (7/6)n_4+1 = (7/6)(7^5m_4+14400)+1. For integer value, m_4\mod 6 = 0, so write m_4 = 6m_3. Then n_3 = (7/6)(7^5(6m_3)+14400)+1 = 7^6m_3+16801.

n_2 = (7/6)n_3+1 = (7/6)(7^6m_3+16801)+1. For integer value, m_6\mod 6 = 5, so write m_3 = 6m_2+5. Then n_2 = (7/6)(7^6(6m_2+5)+16801)+1 = 7^7m_2+705888.

n_1 = (7/6)n_2+1 = (7/6)(7^7m_2+705888)+1. For integer value, m_2\mod 6 = 0, so write m_2 = 6m_1. Then n_1 = (7/6)(7^7(6m_1)+705888)+1 = 7^8m_1+823537. The smallest value corresponds to m_1 = 0 so n_1^{min} = 823537.

These pirates were either very sleepy, or incredibly quick at counting coconuts.

Riddler Classic for 23 March 2018 (part 2)

We’ve seen a generalization of the problem to multiplicative factors other than 2 and bases other than 10. A third generalization would be to shift more than one digit.

Take a positive integer j in base b and move its last m digits to the front. What is the smallest j such that when you do this, the result k is exactly p times j (where p is in the range [2,b-1 ] )?

Let j= b^m \times y+x, where b^{m-1}\le x< b^m . So the digits of x are the final m digits of j and the initial m digits of k, and the digits of y are the remaining digits of both. Let n be the number of digits in y. Then we require

p(b^my+x)= b^nx+y.

Solving, (pb^m-1)y=(b^n-p)x or

y= \frac{b^n -p}{pb^m-1}x .

Now let g=\gcd(pb^m-1,x) and let w=x/g, v=(pb^m-1)/g. Then

y= \frac{b^n-p}{v}w

and since v and w are relatively prime, we must have

b^n=p\mod v.

So we must calculate pb^m-1 and then, for each possible value of x, obtain v and look for the least n that satisfies the above relation. (The minimal value of x is in fact not b^{m-1} but pb^{m-1}, since there can be no carry to an additional digit when j is multiplied by p.) Then we can compute y, and verify that it does indeed have n digits. The smallest such y and associated x solve the problem.

If (pb^m-1) is prime, then v = (pb^m-1) for all possible x and the smallest k results when x=pb^{m-1}. But if (pb^m-1) has a common factor with some x, then v is some factor of (pb^m-1). Generally n, the number of digits in y, is on the order of v, so when (pb^m-1) is prime the solution tends to be many orders of magnitude larger than when it is not.

For instance, consider p=3 and b=10. For m=2, (pb^m-1)=299=13\times 23. In that case some values of x have a common factor with (pb^m-1). E.g., x=46 gives

y= \frac{10^n-3}{13}w

where

10^n=3\mod 13.

The solution is n=4, leading to

j=153846, k=3j=461538.

But for m=1, (pb^m-1)=29 is prime. The number of digits in y then turns out to be 27, and

j=1034482758620689655172413793.

And for m=3, (pb^m-1)=2999 is prime too. We end up with the 1499 digit solution

j = 100033344448149383127709236412137379126375458486162054018006\\ 0020006668889629876625541847282427475825275091697232410803601200\\ 4001333777925975325108369456485495165055018339446482160720240080\\ 0266755585195065021673891297099033011003667889296432144048016005\\ 3351117039013004334778259419806602200733577859286428809603201067\\ 0223407802600866955651883961320440146715571857285761920640213404\\ 4681560520173391130376792264088029343114371457152384128042680893\\ 6312104034678226075358452817605868622874291430476825608536178726\\ 2420806935645215071690563521173724574858286095365121707235745248\\ 4161387129043014338112704234744914971657219073024341447149049683\\ 2277425808602867622540846948982994331443814604868289429809936645\\ 5485161720573524508169389796598866288762920973657885961987329109\\ 7032344114704901633877959319773257752584194731577192397465821940\\ 6468822940980326775591863954651550516838946315438479493164388129\\ 3764588196065355118372790930310103367789263087695898632877625875\\ 2917639213071023674558186062020673557852617539179726575525175058\\ 3527842614204734911637212404134711570523507835945315105035011670\\ 5568522840946982327442480826942314104701567189063021007002334111\\ 3704568189396465488496165388462820940313437812604201400466822274\\ 0913637879293097699233077692564188062687562520840280093364454818\\ 2727575858619539846615538512837612537512504168056018672890963654\\ 5515171723907969323107702567522507502500833611203734578192730910\\ 3034344781593864621540513504501500500166722240746915638546182060\\ 6868956318772924308102700900300.

If you’d asked me to guess, before I worked any of this out, the order of magnitude of the smallest positive integer which is exactly tripled when you move the last three digits to the front, I’m pretty sure I would have seriously underestimated it.

Riddler Classic for 23 March 2018

Spoiler for last week’s fivethirtyeight.com Riddler Classic:

From Joseph Converse, a puzzle of digital manipulation:

Imagine taking a number and moving its last digit to the front. For example, 1,234 would become 4,123. What is the smallest positive integer such that when you do this, the result is exactly double the original number? (For bonus points, solve this one without a computer.)

One way

Write the number (call it m) as 10y+x, where x<10; for instance, for 1,234, y=123 and x=4. Let n be the number of digits in y; then the number resulting from moving the last digit to the front is 10^nx+y. We want 2(10y+x)=10^nx+y.

Solving, we get y = (10^n-2)x/19. Now, 19 is prime and x<10 so isn’t a multiple of 19, and therefore (10^n-2) must be, that is, 10^n\mod 19 = 2.

Going ahead and doing the long division ― that is, dividing 100, 1000, 10000… by 19 until a remainder of 2 is found ― we get n=17; (10^{17}-2)/19 = 5263157894736842. That has 16 digits, so x=1 won’t work; x=2 will give us a 17-digit y=10526315789473684, though. So the smallest number that works is m = 105263157894736842 = 210526315789473684/2.

Another way

We require 2m to have the same number of digits as m, and that means the first digit of 2m can’t be 1. So let’s try making it 2. Then that’s also the last digit of m.

Now, the last digit of 2m is 4, which is also the second to last digit of m. And then the second to last digit of 2m is 8, which must be the third to last digit of m. Then the third to last digit of 2m is 6, with a carry. That means the fourth to last digit of m is 6 and the fourth to last digit of 2m is 3, with a carry.

And so on, until we reach a place where the digit of m is 1 and 2m is 2 without a carry. Stop there. Follow that procedure and you get n = 105263157894736842 as before.

Except we don’t know that this is the smallest answer. We need to do the same with last digit of m running from 3 to 9. In fact (and as you’d expect having seen the other method) this is the smallest.

I’m rather surprised the second way didn’t occur to me sooner; it seems a good deal more obvious in retrospect. Then again, had I done it first I think I might’ve looked at the size of the result and been unconfident I hadn’t overlooked something that might give a smaller answer. The first method confirms it and makes it more clear, I think, that this really is the minimum. It also provides the insight that the answer is not just a mysterious sequence of digits but is connected with the decimal representation of 1/19.

Triple?

Instead of moving the digit to get multiplication by 2, what about by 3? Or by k generally? Adapting either method, one finds moving the last digit of 1034482758620689655172413793 to the front gives triple that number. For quadrupling we get a much smaller answer: 102564 = 410256/4. For quintupling we encounter for the first time the necessity of checking all possible last digits, not just the minimum one: Using 5 for the last digit we find 102040816326530612244897959183673469387755, but with 7 we get 142857! This is related to the fact that if you try the first method, you need y = (10^n-5)x/49, and 49 is not prime, so when x=7 we need 10^n \mod 7 = 5 rather than 10^n \mod 49 = 5.

Here’s a table for k = 1 through 9. I am glad the Riddler puzzle didn’t ask for 6 (by hand)… I did these with a spreadsheet.

1 1
2 105263157894736842
3 1034482758620689655172413793
4 102564
5 142857
6 1016949152542372881355932203389830508474576271186440677966
7 1014492753623188405797
8 1012658227848
9 10112359550561797752808988764044943820224719

All your base

Another generalization of the original puzzle is to do it in base b instead of base 10. There’s no solution in binary, as you can figure out by trying to adapt either method above, or just by noting that doubling a number in binary means appending a 0 to the right end, so you can’t double a number and get a number with the same number of binary digits (bits). In base 3, starting with final digit 2 for m, the final digit for 2m is 1 with a carry of 1; 1 for the next digit of m gives 0 for the next digit of 2m with a carry; 0 for m gives 1 for 2m; 1 for m gives 2 for 2m and we’re done: 1012_3 = 2101_3/2. In decimal, that’s 32 and 64. (In higher bases we need to check last digits from 2 to b-1.) Alternatively, we want y = (3^n-2)x/5 and so require 3^n \mod 5 = 2. n = 3 works and then y = 5x. So with x = 2, y = 10 = 101_3 and m = 1012_3.

In all bases from 3 through 10:

3 1012
4 102
5 13
6 1031345242
7 103524563142
8 25
9 10467842
10 105263157894736842

Edit to add:

And if this Python script is bug free, then

\mathrm{10179b72334c73ad1496e2dbd2c4365203047e46699e76b293dd5c8b5986ca406090d8cd44}\\  \mathrm{ded7537cbba27b41da580c131c2ab89cebea70a88550783c5b119263956824ae8e5e1621aa_{15}}

is the smallest base 15 number which is multiplied by (decimal) 10 when the last digit is moved to the front. At 148 digits, it’s the longest such number for all bases up to 16 and all factors up to (base-1).

 

Schizophrenic thinking

Some years ago I wrote up something about schizophrenic numbers. I read about these numbers in one of Clifford Pickover’s books, but he didn’t really get into what made them work the way they do, so I figured it out on my own. I posted it to the web. Now I can’t find a copy in my files or on my computer, and even the Internet Archive fails me — it didn’t archive it.

So I reconstructed it, more or less. I think.

The schizophrenic numbers are defined as follows. To start with we define

f(x) = \begin{cases} 0& \mbox{if } m=0\\10f(m-1)+m& \mbox{if } m>0\end{cases}\\=\sum\limits_{k=0}^{m} 10^{m-k}k

The first several f(m) are

f(0)=0 \\ f(1)=1\\f(2)=12\\f(3)=123\\f(4)=1234\\f(5)=12345\\f(6)=123456\\f(7)=1234567\\f(8)=12345678\\f(9)=123456789\\f(10)=1234567900\\f(11)=12345679011

and so on. Now the mth schizophrenic number is

S(m)=\sqrt{f(2m+1)}

Are any of the f(2m+1) perfect squares (for m>0)? No, they aren’t, as will become evident below. Therefore S(0) is the only rational in the set. The rest are irrational, so should be non-repeating decimals.

But let’s look at S(20)=\sqrt{12345679012345679012345679012345679012341}. Its value is

S(20)=111111111111111111111.111111111111111111...

Wat.

It can’t be a rational number, unless it’s an integer, and it’s not an integer. What’s going on? Let’s get some more significant figures.

S(20)=111111111111111111111.11111111111111111109005...

Oh, okay, that’s better. It’s not a repeating decimal after all…

S(20)=111111111111111111111.1111111111111111110900555555\\5555555555555555555555555555555...

Wat.

S(20)=111111111111111111111.1111111111111111110900555555\\555555555555555555555555555555535605416...

Um, okay?

S(20)=111111111111111111111.1111111111111111110900555555\\555555555555555555555555555555535605416666666666666666666...

Wat.

Seems not to be able to make up its mind whether to be rational or not. Hence schizophrenic. Here’s about 500 decimal places, broken up into “rational” and “irrational” pieces:

S(20)=111111111111111111111.111111111111111111 \\ 0900\\5555555555555555555555555555555555555\\3560541\\666666666666666666666666666666666\\2886115347\\22222222222222222222222222222\\1326704128428819\\444444444444444444444444\\2068634941610546874\\999999999999999999999\\32467614881946461588541\\6666666666666666\\465564871268691522639973958\\333333333333\\2714065492129693624196136474609374\\999999\\804414573486517125197501992119683159722159\\214377070903714104597488983578152126715487\\497795899993976792215472407658894849931527\\56767644661366482...

(I calculated that by hand. HA HA HA no actually I used a Python script, with the mpmath library.) The repeating pieces get shorter and shorter, the non-repeating pieces get longer and longer, and then (apparently) the repetition stops (aside from random repeats) and it finally starts behaving like we expect irrational numbers to do.

I mean, sure, we all know there exist an infinite number of irrationals that have arbitrarily large (but finite) numbers of repeating digits in them. But who’d expect behavior like this from the square root of an integer? What’s going on?

Well, observe that if x = 0.0123456790123456790123... then

10^9x = 12345679.0123456790123456790123...=12345679+x \\ \Rightarrow x=12345679/999999999=1/81

So f(m) is a little smaller than 10^{m+1}/81. In particular you can see if you think about it, and you can prove inductively using the recurrence formula for f(m), that

f(m)=10^{m+1}/81-(10+9m)/81

which means

S(m)=\sqrt{10^{2m+2}/81-(19+18m)/81} \\ =\frac{10^{m+1}}{9}\sqrt{1-\frac{19+18m}{10^{2m+2}}}

Now you can use the Taylor series expansion

\sqrt{1-y} = 1-y/2-y^2/4-y^3/8-5y^4/128....

Here y is (19+18m)/10^{2m+2}, which for large m is a bunch of zeros after the decimal point, followed by a few digits. In the expansion the terms after the first are powers of y multiplied by an integer and divided by powers of 2, which for higher powers are lots of zeros after the decimal point, followed by some digits. The infinite sum gets divided by 9 — which turns the first term into 0.11111... and each of the following terms into zeros after the decimal point, followed by some digits, followed by some digit repeating to infinity — and then multiplied by 10^{m+1}, which just shifts the decimal point. Look at the first few terms for S(5):

111111.111111... \\ -0.0000060555555...\\-0.000000000000000165013888888...\\-0.0000000000000000000000000089932569444444...\\-0.0000000000000000000000000056207855902777777...

For the first three terms, there are enough zeros in the subsequent term to preserve some of the repeating digits in the sum. The fifth term, though, scribbles over the repeating 4s in the fourth term, and so we only see three sets of repeating digits in S(5):

S(5)=111111.111105055555555390541666657673409...

But for larger m, each term has more leading zeros due to the power of 10^{2m+2} in the denominator, and more terms contribute repeating digits before the scribble-over point is reached. (And you get more and more 1s before and after the decimal point; in other words, you get closer and closer to a power of 10 times 1/9, so no, none of the corresponding f(m) are perfect squares.) I referred somewhat facetiously to “rational” and “irrational” pieces above, but it’s sort of true; the repeating digits are where you can see that there is a finite number of rational terms in the Taylor series contributing to the sum.