Puzzles/Lucky 7s
From http://www.itasoftware.com/careers/eng/job1.php
Find the sum of all the integers between 1 and 10^11 that are both divisible by seven and, when the decimal digits are reversed, are still divisible by seven.
Explorations
f n finds all the numbers less than n having the lucky-7 property. (n must be a power of 10 for f to work properly.) We'll use it to get some idea of the size of problem.
f=: 3 : 0 " 0 x #~ 0 = 7 | |. |.&.": x=. 7*i.>.y.%7 ) f 1000 0 7 70 77 161 168 252 259 343 434 525 595 616 686 700 707 770 777 861 868 952 959
In this sample, a high proportion of the numbers are palindromic.
d g x expands x into d decimal digits:
g=:{.@(0&".)"0@:":"0
3 g f 1000
0 0 0
0 0 7
0 7 0
0 7 7
1 6 1
1 6 8
2 5 2
...
We observe that all these numbers are palindromic if the digits are considered mod 7:
y=:3 g f 1000 (-:|.)"1 ] 7|y 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Sadly, this property does not continue for larger arguments to f:
10 {. (-:|.)"1 ] 7|4 g f 1e4
1 1 1 0 0 0 0 0 0 0 ...
However, with the digits taken mod 7, there are fewer unique numbers with this property:
#~.7|y 7 10#."1 ~. 7|y 0 161 252 343 434 525 616
The Number of Such Numbers
x=: 10^2 3 4 5 ] n=: #@f x 4 22 206 2113 n %. x^/0 1 2 1.81762 0.0203393 7.72482e_9
A quadratic fit gives a very small coefficient for the 2nd degree term, so the function is not a 2nd degree polynomial.
n %. (x^/0 1),.^.x 10.6853 0.0212195 _1.71305 ] b=: n %. (x^/0 1),.^.x 10.6853 0.0212195 _1.71305 n 4 22 206 2113 b +/ .*~ (x^/0 1),.^.x 4.91837 20.0714 207.102 2112.91 b +/ .*~ 1, 1e6, ^. 1e6 21206.5 #@f 1e6 20728
A fit of b0+(b1*n)+b2*^.n gives good agreement. Therefore, the estimated number of such numbers is:
b +/ .*~ 1, 1e11, ^. 1e11 2.12195e9
That is, we are looking at computing the sum of 2 billion numbers. (There may be properties that would permit computing the sum without actually doing 2 billion additions.)
The Sum
] s=: +/@f x 154 10787 1029567 105714126 s %. x^/0 1 2 1821.41 _3.24629 0.0106037 c=: s %. x^/0 1 2 c +/ .*~ x^/0 1 2 1602.82 9178.81 1.02973e6 1.05714e8 c +/ .*~ 1e6 ^/ 0 1 2 1.06004e10 +/@f 1e6 1.0364e10 c +/ .*~ 1e11 ^/ 0 1 2 1.06037e20
A quadratic fit gives a good approximation. The sum of lucky-7 numbers is about 1e20 . Extended precision integers will be required if the sum is to be computed directly.
Other Properties
Comparing the number of lucky-7 numbers against those of them that are palindromic:
(# ,+/@(= |.&.":"0)) f 1e3 22 15 (# ,+/@(= |.&.":"0)) f 1e4 206 33 (# ,+/@(= |.&.":"0)) f 1e5 2113 164
So much for that idea.
Exponential Residues
Powers of 10, modulo 7, are cyclic:
7| 10^i.11 1 3 2 6 4 5 1 3 2 6 4
Any multiple of these powers (except multiples of 7, which always have a residue of 0) follows a similar pattern (but each multiple may start at a different point in this cycle):
7| 2*10^i.11 2 6 4 5 1 3 2 6 4 5 1 7|i. 10 0 1 2 3 4 5 6 0 1 2 7| 10 * i. 10 0 3 6 2 5 1 4 0 3 6 7| 100 * i. 10 0 2 4 6 1 3 5 0 2 4 7| 1000 * i. 10 0 6 5 4 3 2 1 0 6 5 7| 10000 * i. 10 0 4 1 5 2 6 3 0 4 1 7| 100000 * i. 10 0 5 3 1 6 4 2 0 5 3 7| 1000000 * i. 10 0 1 2 3 4 5 6 0 1 2
Also, note that 3 = 7|10, thus the residue 7|x.*10^y. is:
resexp10=: 7: | [ * 10"_ ^ ] resexp10=: 7: | [ * 3: ^ ] 2 resexp10 i.11 2 6 4 5 1 3 2 6 4 5 1
Brute Force
Here's a brutally simplistic implementation of the algorithm:
lucky7a=: ([: +/@f 10"_ ^ ])"0
This is too simple to solve the problem. However, the values obtained from this implementation can be used to test more elaborate implementations:
lucky7a i. 6 0 7 154 10787 1029567 105714126
Solutions
Rather than computing everything at once, we can break the numbers in half, and compute totals and residues independently, then combine. The brute force solution relies on finding numbers which satisfy two conditions (0 = 7 | number) and (0 = 7 | reversed number). However, rather than only computing the "success" cases, we can calculate these residues for every number.
Then, to combine them, we can rely on the fact that (7 | a + b) = (7 | (7 | a) + 7 | b). This tells us which final category each of the intermediate totals belongs. We combine intermediate totals using simple addition. (Intermediate totals are obtained through addition and multiplication)
In other words, when we're categorizing numbers we only need to worry about their 7| residue, and the 7| residue of their reverse. We also track how many numbers there are in each category and their totals. And, we abstract out powers of 10 to make the intermediate values a bit more tractable.
For example when computing the lucky7 total for four digit numbers, one of the numbers which must be included is 9681. If we break this into two pieces, they are 96 and 81. When we classify the first piece, 7|96 is 5, and 7|69 is 6, and there are two numbers that have this characteristic: 26 and 96, and their total is 122. Likewise for the second piece, 7 | 81 is 4 and 7 | 18 is 4, and there are four numbers that have this characteristic: 11, 18, 81 and 88 -- their total is 198. When we combine these combinations, we are finding the total of 2611 2618 2681 2688, 9611 9618 9681 9688. This intermediate total is (122*100*4) + 198*2. (Exercise for the reader: work through a different example and also work through how the categorizing numbers are combined.)
These implementations use =: (instead of =.) so that intermediate values may be easily examined:
revmod7=: 7: | |."1&.(10&#.^:_1)
resexp10=: 7: | [ * 3: ^ ]
lucky7b=: verb define"0
n=: y.-m=: >.y.%2
jnub=: ~. jkey=: 7 | j ,. revmod7 j=: i. 10^m
jtally=: jkey #/. j
jsum=: jkey +//. j
knub=: ~. kkey=: 7 | k ,. revmod7 k=: i. 10^n
ktally=: kkey #/. k
ksum=: (10x^m)*kkey +//. k
rkey1=: knub (resexp10&m@[ + ])"0/&({."1"_) jnub
rkey2=: knub ([ + resexp10&n@])"0/&({:"1"_) jnub
rval=: (ksum */ jtally) + (ktally */ jsum)
{. (7| rkey1 ,.&, rkey2) +//. , rval
)
We can use {. to locate the desired total because the key 0 0 (obtained from 7| number, reverse) always comes first.
,.lucky7b i. 12
0
7
154
10787
1029567
105714126
10363989636
1027216680497
102184086890270
10205609904879424
1020424310227628614
102049428685193293045
This is a bit slow, but it works.
It's possible to use this combining mechanism iteratively. This produces the result more quickly:
lucky7c=: verb define"0
sum=: ,0
nub=: 1 2$ 0
tally=: ,1
knub=: ~. kkey=: 7 | k=: i. 10
ktally=: kkey #/. k
for_m. i. y. do.
ksum=: (10x^m) * kkey +//. k
rkey1=: (knub resexp10 m) +/ {."1 nub
rkey2=: knub +/ ({:"1 nub) resexp10 1
nub=: ~. key=: 7|rkey1 ,.&, rkey2
rval=: (ksum */ tally) + (ktally */ sum)
sum=: key +//. , rval
tally=: key +//. , ktally */ tally
end.
{.sum
)
(,.lucky7c) i. 12
0 0
1 7
2 154
3 10787
4 1029567
5 105714126
6 10363989636
7 1027216680497
8 102184086890270
9 10205609904879424
10 1020424310227628614
11 102049428685193293045
Here we've also used the identity between 7 | number and 7 | reverse for single digit numbers.
Some people might prefer a slightly less verbose implementation (same basic algorithm as lucky7c):
L7=: 3 :0"0
U=. 2 1$T=. 0*N=. ,1
u=. ~.m=. 7|k=. i.10
t=. m +//. k
n=. m #/. k
for_e. i. y. do.
U=. |:~. M=. 7|((u*3^e)+/{.U) ,.&, u+/3*{:U
T=. M +//. ,(t*/N) + n*/T
N=. M +//. , n*/N
t=. t*10x end.
{.T
)