Problems & Puzzles:
Puzzles
Puzzle 104. Numbers that are equal to the sum of cubes of its third parts
(as strings)
Example:
333667001
= 333^{3} + 667^{3} +001^{3}
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 10^{10.}
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 earthshattering, just straightforward code ready to scan the
numbers. The program is standalone and tailormade 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*100000000A*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^mx (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^{m1}=b/10.
the equation above can be rewritten as (2y1)^2 + (2xb)^2 = b^2 + 1. As
a result, if (x,y) i a solution, then so is (bx, 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(2y1) ad v=2xb. we have 0 <= v < b and 0<=u<2b1.
however, u^2 = b^2+1v^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=(2y1)^2+(2xb)^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 nth
parts.
In fact, for n>3, no solution exists. indeed, the problem may be
written sum_{k=0,..., n1} {x_k*b^k}
= sum {x_k^2}. but the latter term is <= n*(b1)^2, while the left
hand one is >= b^{n1} > n*(b1)^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=2z1, v=abs(2yb) and w=b^22x. 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 by. 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^2Sx+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^2b, or
b(b1). 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
fourdigit solutions. Note there is a way to check for a number being of
the form b(b1). Multiply it by 4, and add 1  the result should be a
perfect square (of 2b1).
Now to use this in a search. We need to choose n, and vary a. For
each a value calculate X=4(10^na)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^n1 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^(F1)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 subpuzzle!"
***
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}n1 {1}1
or written as one number
{9}n {0}n {9}n {0}n1 {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 APRTCLE 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 lookalike
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^{mr}  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^(F1)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^2xy+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.
***
