Problems & Puzzles: Puzzles

Puzzle 104. Numbers that are equal to the sum of cubes of its third parts (as strings)

Example:

333667001 = 3333 + 6673 +0013

Here are the first 23 of these numbers below 10^10 (*)

153, 370, 371, 407, 165033, 221859, 336700, 336701, 340067, 341067, 407000, 407001, 444664, 487215, 982827, 983221, 166500333, 296584415, 333667000, 333667001, 334000667, 710656413, 828538472,

BTW, 333667001 is the only (& then the least) prime of this kind of numbers below 1010.

Questions:

1. I have some empirical evidence that this sequence is infinite. Can you give a formal proof of it?
2. Find the following two primes in the sequence.

Generalizing the concept you may construct the following sequences:

a) Numbers that are equal to the sum of the squares of its halves.
b) Numbers that are equal to the sum of the four power of its fourth parts.
c) etc.

3. Obtain the corresponding sequences and remark the primes within.

(*) Note:The first 16 numbers can be found at pp. 65 & 101, "Exploring number theory with microcomputers", D. D. Spencer. I just calculated the last seven members. The first 4 numbers are also called "Narcissistic" or "Armstrong" numbers.

 


Solution

Patrick De Geest explored (20/8/2000) the question 2.a. Here are his interesting results and observations!...

"In the hope of finding prime solutions I started programming sub question 2a (numbers equal to the sum of the squares of its halves). The reason is because I remembered Harvey Heinz had some of these numbers published (not an exhaustive list btw) on his page about Narcissistic numbers : see www.geocities.com/CapeCanaveral/Launchpad/4057/ 

Here is the full list I got from my programming efforts. Curiously enough these solutions seems to come in pairs so now are 'two halves', 'squares' and 'pairs' involved :-) [bolds are mine, CR]

---------------------------------------------------

L = 2 (nihil)

---------------------------------------------------

L = 4 (1 pair)

12_33 = 12^2 + 33^2 ()
88_33 = 88^2 + 33^2 ()

Note that the sum of the 'left halves' of each pair always add up to the nearest multiple of 10, in the above case 12 + 88 = 100. The 'right halves' are always identical.

---------------------------------------------------

L = 6 (1 pair)

010_100 = 010^2 + 100^2
990_100 = 990^2 + 100^2 ()

---------------------------------------------------

L = 8 (1 pair)

0588_2353 = 0588^2 + 2353^2 *** PRIME ***
9412_2353 = 9412^2 + 2353^2 ()

Note that 5882353 is PRIME !

---------------------------------------------------

L = 10 (3 pairs)

00990_09901 = 00990^2 + 09901^2
99010_09901 = 99010^2 + 09901^2
17650_38125 = 17650^2 + 38125^2 ()
82350_38125 = 82350^2 + 38125^2 ()
25840_43776 = 25840^2 + 43776^2 ()
74160_43776 = 74160^2 + 43776^2 ()

---------------------------------------------------

L = 12 (3 pairs)

000100_010000 = 000100^2 + 010000^2
999900_010000 = 999900^2 + 010000^2
116788_321168 = 116788^2 + 321168^2 ()
883212_321168 = 883212^2 + 321168^2 ()
123288_328768 = 123288^2 + 328768^2 ()
876712_328768 = 876712^2 + 328768^2 ()

---------------------------------------------------

L = 14 (7 pairs)

0004860_0220401 = 0004860^2 + 0220401^2
9995140_0220401 = 9995140^2 + 0220401^2
0060130_0773101 = 0060130^2 + 0773101^2
9939870_0773101 = 9939870^2 + 0773101^2
0099010_0990100 = 0099010^2 + 0990100^2
9900990_0990100 = 9900990^2 + 0990100^2
0768180_2663025 = 0768180^2 + 2663025^2
9231820_2663025 = 9231820^2 + 2663025^2 ()
0889680_2846976 = 0889680^2 + 2846976^2
9110320_2846976 = 9110320^2 + 2846976^2 ()
1379310_3448276 = 1379310^2 + 3448276^2 ()
8620690_3448276 = 8620690^2 + 3448276^2 ()
1534830_3604525 = 1534830^2 + 3604525^2 ()
8465170_3604525 = 8465170^2 + 3604525^2 ()

---------------------------------------------------

Lengths 4, 6, 10, 12 and 14 only yield composites, alas. When I have the time I'll explore longer numbers. The solution marked with () are genuine as they don't need leading zero's."

***

Can someone explain the Patrick's observations about this kind of numbers?

***

One day after(21/08/2000) Patrick sent this:

L = 16 (15 pairs) : no primes found

01060588_10243728 = 01060588^2 + 10243728^2
98939412_10243728 = 98939412^2 + 10243728^2 ()
01689688_12888513 = 01689688^2 + 12888513^2
98310312_12888513 = 98310312^2 + 12888513^2 ()
02496100_15600625 = 02496100^2 + 15600625^2
97503900_15600625 = 97503900^2 + 15600625^2 ()
03135760_17428225 = 03135760^2 + 17428225^2
96864240_17428225 = 96864240^2 + 17428225^2 ()
06699912_25002048 = 06699912^2 + 25002048^2
93300088_25002048 = 93300088^2 + 25002048^2 ()
08122812_27318513 = 08122812^2 + 27318513^2
91877188_27318513 = 91877188^2 + 27318513^2 ()
10913140_31180401 = 10913140^2 + 31180401^2 ()
89086860_31180401 = 89086860^2 + 31180401^2 ()
18130312_38526913 = 18130312^2 + 38526913^2 ()
81869688_38526913 = 81869688^2 + 38526913^2 ()
20271412_40202128 = 20271412^2 + 40202128^2 ()
79728588_40202128 = 79728588^2 + 40202128^2 ()
23429560_42355776 = 23429560^2 + 42355776^2 ()
76570440_42355776 = 76570440^2 + 42355776^2 ()
29138400_45440001 = 29138400^2 + 45440001^2 ()
70861600_45440001 = 70861600^2 + 45440001^2 ()
31742188_46547313 = 31742188^2 + 46547313^2 ()
68257812_46547313 = 68257812^2 + 46547313^2 ()
34299088_47470848 = 34299088^2 + 47470848^2 ()
65700912_47470848 = 65700912^2 + 47470848^2 ()
37971540_48531600 = 37971540^2 + 48531600^2 ()
62028460_48531600 = 62028460^2 + 48531600^2 ()
44357700_49680625 = 44357700^2 + 49680625^2 ()
55642300_49680625 = 55642300^2 + 49680625^2 ()

----------------------------------------------------------

Also I'll reproduce my program with which I did the search. This version is 'prepared' to look for L=16 ! I guess it is nothing earth-shattering, just straightforward code ready to scan the numbers. The program is standalone and tailor-made for the sums of squares and cannot be amended for the other cases of puzzle 104.

10 for A=2 to 50000000 step 2
20 Z=ceil(sqrt(A*100000000-A*A))
30 X=A*100000000+Z:Q=A*A+Z*Z
40 if val(left(str(Q),(alen(X)-7)))>A then 80
50 print X,A,Z;chr(13);
60 if Q=X then color 10:print X,A,Z:color 15:beep
70 inc Z:goto 30
80 next A

***

The 22/08/2000 Mahmoud Chilali solved the "sum of squares" problem and the Patrick's observations about them. Here is his interesting proof:

I solved the "sum of squares" case. In particular: there are infinitely many numbers that are the sum of their halves squares. More precisely: there exists a number of 2m digits that is the sum of its halves squares if and only if 10^{2m} +1 is not prime. Note that 10^{2*m}+1 is composite if m is not a power of two. This resembles Fermat numbers!

If a number is the sum of halves squares x^2+y^2, then so is the number obtained by replacing x with 10^m-x (where m is half the number of digits of the full number).

The problem amounts to finding pairs x and y such that b*x + y = x^2 +y^2, where b=10^m, 0<x<b, 0<y<b. If leading zeros are not allowed, then x must have exactly m digits, so x>=10^{m-1}=b/10. the equation above can be rewritten as (2y-1)^2 + (2x-b)^2 = b^2 + 1. As a result, if (x,y) i a solution, then so is (b-x, y) , which explains Patrick's remark. We can thus reduce the search to (x,y) such that 2x>=b.

The problem amounts to finding a decomposition of b^2+1 as the sum of two squares, with some conditions on the numbers (the conditions on x and y). Let us write b^2+1 = u^2+v^2 where u is odd and v is even (remember that b is even), and both ar >=0. now let us translate the conditions on (x,y) to conditions on u and v. we should have: u=abs(2y-1) ad v=2x-b. we have 0 <= v < b and 0<=u<2b-1. however, u^2 = b^2+1-v^2 shows that u<=b. it is easy to see that v=0 is impossible, and since u is odd, u>=1.

We end with the problem: find integers u and v, such that 1<=u<b, 1<=v<b, such that b^2+1=u^2+v^2.
* If b^2+1 is prime, then the only way to write it as the sum of two squares is b^2+1^2. so there is no u and v satisfying the above. Hence, there is no corresponding x and y.
* If b^2+1 is not prime, it may be written as the product of two integers, that are themselves the sums of two squares: b^2+1 = (t^2+s^2)(f^2+g^2). This is true since all the prime divisors of b^2+1 are of the form 4k+1 (-1 is a square modulo these primes). We can assume (t^2+s^2) <= b (if both member were > b, then their product would be >= (b+1)^2 > b^2+1). From this representation, one can write b^2+1 = (t*f + s*g)^2 + (t*g - s*f)^2 = (t*f - s*g)^2 + (t*g + s*f)^2 and derive u and v, and finally x and y. The sought number is then N=(2y-1)^2+(2x-b)^2=(b^2+1+u+vb)/2. for N to be prime, u must be =1 modulo 4 (otherwise, N is even).

Algorithm to find a number of 2m digits satisfying the condition (sum of squares):

- compute X = 10^{2m} +1.
- start with d=2
- y = sqrt(X - d^2). if d^2+y^2=X, derive a solution. else do nothing
- if d>=y, stop (if no solutions found, then X is prime)
- d =d +1. retry.

an example (yet to be checked though):

L=16:
50000340_00021648
50017522_00012717
50017114_00013261
and the symmetric ones (x -> 10^8 -x).


Generalization:

- find numbers that are the sums of the squares of their third parts.
- more generally, find numbers that are the sum of squares of their n-th parts.
In fact, for n>3, no solution exists. indeed, the problem may be written
sum_{k=0,..., n-1} {x_k*b^k} = sum {x_k^2}. but the latter term is <= n*(b-1)^2, while the left hand one is >= b^{n-1} > n*(b-1)^2 for n>=4. for the case n=3, we can use the same method to end with: 1+b^2+b^4 = u^2 + v^2 + w^2, where u=2z-1, v=abs(2y-b) and w=b^2-2x. the sought number is then x^2+y^2+z^2 = x*b^2 + y*b +z. note that we still have the symmetry property: y may be replaced with b-y. What are the exact conditions that guarantee the existence of u,v and w satisfying the above (with the bound conditions: 0<= x,y,z <b, x>b/10 if leading zeros are not allowed....).

***

The 23/08/2000 I received two very interesting communications from Chris Nash, both related to the "sum of squares of two halves", providing more light about this part of the puzzle:

"I have some explanations about Patrick de Geest's results from his search for numbers that are 'squares of two halves'. Let the number be of length 2n digits, let the first n digits be a, and the second n digits be b. Then we have

a.10^n + b = a^2 + b^2

rearranging

a^2 - a.10^n - b + b^2 =0.

Choose a value for b, and view this as a quadratic equation in a. Remember that if x^2-Sx+P is a quadratic equation, the sum of the roots is S, and the product is P.

So in this case the sum of the roots for a is 10^n. In other words, for a given value of b, if solutions a exist, they come in pairs that sum to 10^n. Note also that the product of the roots is b^2-b, or b(b-1). This gives us a very quick way to check solutions - for instance it is not difficult to show that 12*88=33*32, and so 1233, 8833 are four-digit solutions. Note there is a way to check for a number being of the form b(b-1). Multiply it by 4, and add 1 - the result should be a perfect square (of 2b-1).

Now to use this in a search. We need to choose n, and vary a. For each a value calculate X=4(10^n-a)a+1 and check if it is a perfect square.

There are very fast ways to quickly check if a number is *not* a perfect square, by considering its value modulo a prime number and checking the quadratic residue symbol. But note there are some very quick things we can determine, for example, we can tell what is the last digit of this expression for each last digit of a, and quickly see whether it can ever be a perfect square. For example, it is not possible for the last digit of a to be 1, 4, 6, or 9 - in those cases, X ends in a 7, and so cannot be a square."

Later, the same day and responding to my question, "Have you seen the Mahmoud's collaboration posted yesterday night?", he wrote:

" I just checked that out, and there appear to be some errors with his reasoning, for his examples do not work (one has first part ending in a 4, which is not possible) - and do not agree with Patrick's listings. I think though the only error is in his calculated results. Note that there are more efficient ways to write b^2+1 as a sum of two squares if the factorization of b^2+1 is known, while searching is difficult if the number of digits is large.

Note that Mahmoud's result predicts that a formula exists to tell you just how many solutions there are to Patrick's problem for a given digit length - it's the number of ways of expressing 10^d+1 as a sum of two squares (you already have an algorithm that solves the sum of two squares problem). Here is Patrick's list of how many pairs he found:

Length, pairs

2, 0
4, 1
6, 1
8, 1
10, 3
12, 3
14, 7
16, 15

Do you see the pattern? *The number of pairs is a Mersenne number*.

To solve this little mystery I looked at the factor tables of 10^n-1 at http://www.cerias.purdue.edu/homes/ssw/cun/main600 (detected broken 1/9/01) and looked at how many factors there are. Here's the list:

Length, factors

2, 1
4, 2
6, 2
8, 2
10, 3
12, 3
14, 4
16, 5

By now you should be able to guess the formula - the number of solutions of length L is equal to 2^(F-1)-1, where F is the number of factors of 10^L+1. For instance, the number of 120 digit solutions is 127, since 10^120+1 has 8 prime factors.

That is quite a lot of new and surprising information... and all this is for the sub-puzzle!"

***

I recall the attention of the readers that these gentlemen (Patrick, Mahmoud & Chris) has only tackled one part of the whole puzzle. So many other interesting things should come in the near future...

***

Patrick De Geest got (25/8/2000) a prime number solution for the case of sum of squares of its halves:

"While my little program was churning up case L = 20 I noticed the following two similar or look_alike solutions :

00990_09901 ( L = 10 ) and 0000999900_0099990001 ( L = 20 )

Maybe I could detect a pattern here so I build a few more like solutions of the form L = 5*n (with n the even numbers 2, 4, 6, 8, 10, ...). In effect I constructed an infinite pattern. Shorthand notation with the two parts of the number :

{0}n {9}n {0}n/2 _ {0}n/2 {9}n {0}n-1 {1}1

or written as one number

{9}n {0}n {9}n {0}n-1 {1}1

The list then starts like this :

L = 10 : 00990_09901
L = 20 : 0000999900_0099990001
L = 30 : 000000999999000_000999999000001
L = 40 : 00000000999999990000_00009999999900000001
L = 50 : 0000000000999999999900000_0000099999999990000000001
etc.

But so far all were composite. So I constructed a small program to set up a loop for higher values of L and tested them for strongpseudoprimeness. This time I had more luck as I found a probable solution for L = 160 ! A quick check with APRT-CLE confirmed it is a genuine prime. (PS my program gave up with an overflow at value L = 1350, so for now this is the only one I discovered)

Here is the number in the above used shorthand notation :

{9}32 {0}32 {9}32 {0}31 {1}1

or written out in full (its real length is 128 digits):

9999999999999999999999999999999900000000000000000000000000000000
9999999999999999999999999999999900000000000000000000000000000001

IS PRIME.

and represented with the two equal halves (with leading zero's) :

00000000000000000000000000000000999999999999999999999999999999990000000000000000^2 +
00000000000000009999999999999999999999999999999900000000000000000000000000000001^2

***

Mahmoud Chilali sent (4/9/2000) the following explanation to the last Patrick's observations:

I tried to get theoretical explanation of Patrick look-alike solutions, so here's what I ended with.

let's look for solutions x and y of the form: x=t.10^r, y=t.10^{2r}+1. this is a solution if and only if (here again, m=L/2). 10^{m-r} - 1 = (10^{2r}+1).t 

one such t exists if m = (4q+1).r for some integer q. we then have: t = (10^{4qr} - 1) / (10^{2r} + 1). so, Patrick's first solution is with r=1, m=5, t=99. as we see, there are infinitely many.

***

Chris Nash provides (28/09/2000) a precision of his own formula for the number of solutions of length L:

"...the number of solutions of length L is *at most* 2^(F-1)-1, where F is the number of factors of 10^L+1. Equality holds if 10^L+1 is squarefree..."

***

As a matter of fact this precision was developed by Chris to solve a question of Patrick who only could discover with his code two pair of solutions instead of the three predicted by the old Chris's formula. Chris revised the original formula and modified as seen but the pairs remain being 3. Then he discovered the third (lost) solution which served at the same time for the discovering of a bug if the line 20 of the Patrick's code.

Here are the solutions for L=18:

L = 18 (3 pairs)

009900990_099009901 = 009900990^2 + 099009901^2
990099010_099009901 = 990099010^2 + 099009901^2

010099990_099989901 = 010099990^2 + 099989901^2
989900010_099989901 = 989900010^2 + 099989901^2

999999000_001000000 = 999999000^2 + 001000000^2
000001000_999000000 = 000001000^2 + 999000000^2

***

Giovanni Resta came up with direct answers to questions about the infinitude of solutions (Nov. 2006):

Hi, apparently nobody answered the part 1 & 2 of your puzzle 104, i.e.,
proving that there are infinite numbers equal to the sum of the cubes of
their third parts, and finding prime such numbers greater than 10^10.

1) It is sufficient to notice that all the numbers of the form
[4][0][7] [34][00][67] [334][000][667] and so on have that property.
since 3333...4 can be expressed as (10^k+2)/3 and
6666...7 as (2*10^k+1)/3 it is sufficient to prove that
[(10^k+2)/3]^3 + [(2*10^k+1)/3]^3 = [(10^k+2)/3]*10^(2k) + [(2*10^k+1)/3]
which is just a matter of a little manipulation.

There are also other such infinite families, for example,
[34][10][67], [3334][0100][6667], [333334][001000][666667], etc.
where the inner part grows by a factor of 10, while the extremal
parts gain 2 digits each at each step.

2) I've checked all the numbers up to 15 digits.
The only primes I found are:

333366670001 = 3333^3 + 6667^3 + 0001^3

8740609620419 = 874^3 + 06096^3 + 20419^3
56482546234141 = 5648^3 + 25462^3 + 34141^3
127684145437883 = 12768^3 + 41454^3 + 37883^3

It is not too difficult to find a larger prime, exploiting one
of the infinite families found in point (1)
(several of which unfortunately only provide multiples of 3).

The numbers of the form [3334][0000][6667] we considered above
are never prime, because of their property.
Indeed, they are equal to [(10^n+2)/3]^3 + [(2*10^n+1)/3]^3.
And since in general x^3+y^3 = (x+y)(x^2-xy+y^2), they
have always at least two factors.

Another infinite family is that which contains numbers like
[3][7][1], [33][67][01], [333][667][001], where a(k) will have 3*k digits.
I'v checked a(n) for n<1000 and it is prime for n=3, 4 (as we already
know) and for n=46, which will provide a nice, certified, prime of 46*3 = 138 digits.

***


Records   |  Conjectures  |  Problems  |  Puzzles