An Algorithm

Figure 1

Algorithms seemingly rule the world. Today I was confronted with my number of the day (25729) and was struggling to find something of interest in it. All I came up with for my Twitter post is shown in Figure 1. Clearly I was clutching at straws but later I noticed an interesting pattern. 2 + 5 is 7 and 7 - 5 is 2 and 7 + 2 is 9. What's happening here can be represented as an algorithm:

ADD the 1st digit to the 2nd digit and put the result to the right of the two digits to form a new number (here the addition yields 7 and so the new number is 257).

SUBTRACT the 2nd digit from the 3rd digit and place the result to the right again to form a new number (here the result of the subtraction is 2 and so the new number is 2572).

ADD the 3rd digit to the 4th digit and place the result to the right again to form a new number (here the result of the addition is 9 and so the new number is 25729).

If this process were repeated two more times, the result would be 25729716. This leads to a problem because with 16 comes a jump in the number of digits. It's probably best to make the rule such that, if the result of the addition is a two digit number, then 10 is subtracted so that a one digit number is returned. This would yield 6 in the case of 16. The number is now 2572976.

Here again we have a problem because subtracting 7 from 6 yield -1. If we stick to our modulus 10 approach, then -1 is really 9. Thus the number becomes 25729769.

The algorithm is thus a repeating addition and subtraction of digit pairs, starting with the addition of the first two digits. What I did next was to investigate what happens to 25729769 as the process continues.

I found that once the digit stream reached 120 digits, the cycle was complete. This could be expressed in terms of a trajectory of length 120. I was interested in what happened with other pairs of starting digits.

There are 90 possibilities starting with 10 (I didn't want leading zeroes) and ending with 99.

Here is what I found (any numbers omitted have a trajectory of 120):

12 --> 24 digits before repeating

17 --> 24 digits before repeating

20 --> 40 digits before repeating

22 --> 40 digits before repeating

24 --> 8 digits before repeating

26 --> 40 digits before repeating

28 --> 40 digits before repeating

29 --> 24 digits before repeating

31 --> 24 digits before repeating

36 --> 24 digits before repeating

40 --> 40 digits before repeating

42 --> 40 digits before repeating

43 --> 24 digits before repeating

44 --> 40 digits before repeating

46 --> 40 digits before repeating

48 --> 8 digits before repeating

50 --> 3 digits before repeating

51 --> 3 digits before repeating

52 --> 3 digits before repeating

53 --> 3 digits before repeating

54 --> 3 digits before repeating

55 --> 3 digits before repeating

56 --> 3 digits before repeating

57 --> 3 digits before repeating

58 --> 3 digits before repeating

59 --> 3 digits before repeating

60 --> 40 digits before repeating

62 --> 8 digits before repeating

64 --> 40 digits before repeating

66 --> 40 digits before repeating

67 --> 24 digits before repeating

68 --> 40 digits before repeating

74 --> 24 digits before repeating

79 --> 24 digits before repeating

80 --> 40 digits before repeating

81 --> 24 digits before repeating

82 --> 40 digits before repeating

84 --> 40 digits before repeating

86 --> 8 digits before repeating

88 --> 40 digits before repeating

93 --> 24 digits before repeating

98 --> 24 digits before repeating

There are 90 numbers between 10 and 99:

• 48 of them have trajectories of 120 digits
• 42 of them have trajectories other than 120

Of these 42:

• 10 have trajectories of 3 (50 to 59)
• 4 have trajectories of 8 (24, 48, 62, 86)
• 12 have trajectories of 24
  (12, 17, 29, 31, 36, 43, 67, 74, 79, 81, 93, 98)
• 16 have trajectories of 40
  (20, 22, 26, 28, 40, 42, 44, 46, 60, 64, 66, 68, 80, 82, 84, 88)

The trajectories of 3, 8, 24 and 40 are all factors of 120 (3 x 40 = 120, 8 x 15 = 120, 24 x 5 = 120, 40 x 3 = 120)

Here is the SageMath code that I used (permalink):

a=2
b=5
number=[a,b]
for i in [1..65]:
    c=(a+b)%10
    number.append(c)
    d=(c-b)%10
    number.append(d)
    a=c
    b=d
string=""
for i in range(0,len(number)):
    string+=str(number[i])
print string 
item=str(number[0])+str(number[1])+str(number[2])
string2=''
for i in range(3,len(number)):
    string2+=str(number[i])
w=Word(string2)
print str(number[0])+str(number[1]),"-->",w.find(item)+3,"digits before repeating"

This produced an output of:

257297695615617637033033639659459439235275279219011011213253853813415495493473077077471451651671875835831891099099897857257297695615
25 --> 120 digits before repeating

The lesson to be drawn from this is that there is something of interest lurking in every number. It's up to us to see it. The fault is in ourselves, not the number. Notice also that the number 42 (the subject of my previous post) makes an appearance in this post (as the number of trajectories between 10 and 99 that are not equal to 120). The real mystery is why 120 is the upper limit and why there isn't a spread of trajectories rather than a clumping of them at 3, 8, 24, 40 and 120.

42

On April 1st 2019, my blog post was titled "42 is the new 33" and that time a solution to the problem of expressing 42 as a sum of three cubes had not been found. However, very recently, a solution was found as this Numberphile Video explains:

The solution is visible there in the thumbnail for the video but I'll repeat it below:$$X^3+Y^3+Z^3=42 \text{ when }$$ \(X = -80538738812075974\) 

\(Y = 80435758145817515\) 

\(Z = 12602123297335631\)

Certain numbers cannot be the sum of three cubes. The reason is that any cubic number must be equal to 0 or ±1 mod 9. If we add three cubic numbers together, the sum must therefore lie between -3 and +3 and so any number that is equal to 4 or 5 mod 9 (or equivalently ±4) cannot be expressed as a sum of three cubes. So between 1 and 99, the following numbers fall into this category: 4, 5, 13, 14, 22, 23, 31, 32, 40, 41, 49, 50, 58, 59, 67, 68, 76, 77, 85, 86, 94, 95.

It wasn't obvious to me why "any cubic number must be equal to 0 or ±1 mod 9". However, I finally realised why this was the case. Here is what I discovered:

Consider a number \(x\) that can be divided, by 9, \(n\) times leaving a remainder of \(r\). This means that \(x=9n +r\) and so \(x^3=(9n+r)^3 \). This latter expression becomes:$$(9n)^3+3 \times (9n)^2 r+ 3 \times (9n)r^2+r^3$$Clearly 9 divides each term of the above expression, except perhaps the \(r^3\) term. Because we are considering modulus 9, the remainder \(r\) must lie between -4 and +4 (-4 is the same as +5, -3 is the same as +6 etc.). Let's consider each possible remainder:

• \(±4^3=±64\) and \(±64 \equiv ±1 \bmod 9\)
• \(±3^3=±27\) and \(±27 \equiv 0 \bmod 9 \)
• \(±2^3=±8\) and \(±8 \equiv ±1 \bmod 9\)
• \(±1^3=±1\) and \(±1 \equiv ±1 \bmod 9 \)
• \(0^3=0\) and \(0 \equiv 0 \bmod 9 \)

So there you have it, any cubic number must be equal to ±1 or 0 and so the sum of three cubes must lie between ±3. This excludes any number that is ±4 or ±5 mod 9.

Here are the numbers from 1 to 99 expressed as a sum of three cubes (zeroes allowed). The table was taken from an old site and I had to manually enter the values for 33, 42 and 74 because they were still empty:

Figure 1: numbers between 1 and 29

Figure 2: numbers between 30 and 64

Figure 3: numbers between 65 and 99

As the YouTube video makes clear, the search is on for a solution to 114, the next "unknown" after 42, but also for a third solution to 3. The two current solutions are \(1^3+1^3+1^3=4^3+4^3+(-5)^3=3\) but is there another solution? As yet, we don't know.

ADDENDUM: LINK

Well actually now we do know:$$ 3=569936821221962380720^{3}+(-569936821113563493509)^{3}+(-472715493453327032)^{3}$$The only remaining unsolved cases up to 1,000 are 114, 165, 390, 579, 627, 633, 732, 906, 921, and 975.