# How to calcuate the sum of 1/x, where x is an integer not containing the digit 9 and 10,000,000 ≤ x ≤ 88,888,888

My code is:

nonine[x_] := If[StringMatchQ[IntegerString[x], "*9*"], False, True];
SetAttribute[nonine, Listable];

tbl = Select[Range[10^2, 888], nonine[#] &];

Total[1.0/tbl]


got out of memory problem.

-
Welcome to mma.se by the way! This looks like a project Euler question, is that right? –  Jacob Akkerboom Mar 13 at 10:56
I found it on zhihu, which is a copycat of Quora in China. –  PhilChang Mar 13 at 11:47
@ErikE there are more numbers containing 9 than numbers that are free of 9. There only has to be one 9 in the entire number. –  Jacob Akkerboom Mar 14 at 1:35
@JacobAkkerboom There is a way to do in microseconds the mere summing of all the numbers: 36 * 11111111 * 9 ^ 7 - 36 * 1111111 * 9 ^ 4. However, I missed that the request was for the sum of 1/x for each number, which is not so simple. My apologies for the mistake. –  ErikE Mar 14 at 15:09
@ErikE, no problem, I appreciate the discussion :). If you follow up your comment with more thinking of your own, you are open minded and you are careful to delete any comments that turn out to have little relevance to the Q&A, like you did/have, then by all means post away (I'd say) :). Not saying you should always remove silly comments, but in a nice Q&A like this it is nice to keep things tidy IMO :). (temporary message) –  Jacob Akkerboom Mar 14 at 15:22

Update

This runs in about half a second:

Total[1.0 ~Divide~ Flatten@Outer[Plus,
Range[0, 8],
Range[0, 80, 10],
Range[0, 800, 100],
Range[0, 8000, 1000],
Range[0, 80000, 10000],
Range[0, 800000, 100000],
Range[0, 8000000, 1000000],
Range[10000000, 80000000, 10000000]]]

(* 1.07145 *)


Original

This is far from elegant, but runs in a couple of seconds:

Compile[{},
Block[{s = 0.},
Do[s += 1./(a + b + c + d + e + f + g + h),
{a, 0, 8},
{b, 0, 80, 10},
{c, 0, 800, 100},
{d, 0, 8000, 1000},
{e, 0, 80000, 10000},
{f, 0, 800000, 100000},
{g, 0, 8000000, 1000000},
{h, 10000000, 80000000, 10000000}];
s]][]

(* 1.07145 *)

-
You beat me to adding Outer. :-) –  Mr.Wizard Mar 13 at 13:39
@Mr.Wizard, I tried Outer originally but kept getting an out of memory crash. The problem was using / for the division, as soon as I put Divide in instead it worked. –  Simon Woods Mar 13 at 13:47
This is amazing (+1)- can you explain why Flatten@Outer[10^8 #1 + 10^7 #2 + 10^6 #3 + 10^5 #4 + 10^4 #5 + 10^3 #6 +10^2 #2 + 10 #1 &, Range[1, 8], Range[0, 8], Range[0, 8], Range[0, 8], Range[0, 8], Range[0, 8], Range[0, 8], Range[0, 8]] takes that much longer? –  gpap Mar 13 at 15:23
@gpap, all those extra multiplications make a difference! That pure function is called nearly 79 million times... –  Simon Woods Mar 13 at 16:35
@SimonWoods ah, I am being daft. Thanks! –  gpap Mar 13 at 16:45

With the definitions

a = 10000000;
b = 88888888;

createLookUp[nn_] :=
Boole[! MemberQ[IntegerDigits[#], 9]] & /@ Range[nn]

unless9Rec = Function[If[! MemberQ[IntegerDigits[#], 9], 1/#, 0]]

cfu =
Compile[
{{a, _Integer}, {b, _Integer}, {lookup, _Integer, 1}}
,
Block[
{sum, len, largeFixedInt, min, max, nn},
largeFixedInt = 0;
sum = 0.;
nn = Length@lookup;
min = Quotient[a, nn, 1] + 1;
max = Quotient[b, nn];
Do[
largeFixedInt = nn*ii;
If[
lookup[[ii]] == 1
,
Do[
If[
lookup[[jj]] == 1,
sum += 1/(largeFixedInt + jj)
]
,
{jj, nn}
];

]
,
{ii, min, max}

];
sum

]

,
CompilationTarget -> "C"
];


We have

(
nn = 1*^4;
lookup = createLookUp[nn]; ;
unless9Rec[a] + cfu[a, b, lookup] - unless9Rec[Ceiling[b, nn]])
) // Timing


{0.358173, 1.07145}

-
It would be a performance hit to always access the lookup table by first subtracting 1. This code should translate to C relatively easily, where arrays start at 0. –  Jacob Akkerboom Mar 13 at 10:27

All the functions you need are compilable, so you might just Compile your code to gain some speed :

sum = Compile[{{start, _Integer}, {end, _Integer}, {digit, _Integer}},
Module[{out = 0., counter = start},
While[counter <= end,
out = out + (1./counter)  Boole[Not[MemberQ[IntegerDigits[counter], digit]]];
counter++] ;
out
]
]

sum[10000000, 88888888, 9] // AbsoluteTiming
(* {18.919000, 1.07145} *)


Compiling to "C" (just add , CompilationTarget -> "C" to the above) :

sumC[10000000, 88888888, 9] // AbsoluteTiming
(* {11.663000, 1.07145} *)


As it is, the code by @RunnyKine is not compilable, so the comparison is not favorable :

(x = 0.;
For[i = 10000000,
i <= 88888888,
i++,
If[StringMatchQ[IntegerString[i], "*9*"] == False,  x += 1./i]
];
x) // AbsoluteTiming
(* {275.261000, 1.07145} *)

-
Nice answer, it seems we get the same results. You are hardcore for waiting the 275 seconds :) –  Jacob Akkerboom Mar 13 at 10:29
@JacobAkkerboom Thanks, but I just left it running and did something else. It probably took you longer to write your (better) code. –  b.gatessucks Mar 13 at 10:33
Yeah, I guess so, it took me a while to get it right. I always take long, that's my secret :P. I have to make up for it with fast code ;). By the way it was nice to see we had exactly the same code for testing if the IntegerDigits contained a 9. –  Jacob Akkerboom Mar 13 at 10:39

You're creating much more work than needed, try something like:

Sum[1/FromDigits[IntegerDigits[x, 9]], {x, 4782969, 43046720}]


This should complete on any machine with decent memory size (I'm on netbook at moment, can't verify that). Use N inside sum if arbitrary precision is not needed.

The structure of the digits in your query should be a clue...

Edit: This completed (took a while) on my netbook using machine precision, so should certainly be fine on a "real" machine at arbitrary precision. Using the clue, probably even a more direct way to get this. Of course, compile away if a precise answer is not needed.

Another way of doing this directly without the wasted work of a naive solution is:

Total@(1/FromDigits /@ Tuples[Join[{Range[8]}, ConstantArray[Range[0, 8], 7]]])


This again only operates on the numbers that matter, generated rather than filtered and wasting time. A similar construct can trivially be adapted to any conditions, e.g. "No nines anywhere and no 6 in the sixth digit", etc.

Neat question, and a good example of speed via thinking about the characteristics of the problem (naive brute-force is doing over double the work needed to solve this) vs speeding up unneeded work.

-

A functional version is not that terrible in 29 seconds:

AbsoluteTiming@
Fold[#1 + If[MemberQ[IntegerDigits[#2], 9], 0., 1./#2] &, 0.,
Range[10000000, 88888888]]


{28.718411, 1.07145}

but if you go to arbitrary precision arithmetic it becomes prohibitive I think.

-

You are asking Mathematica to compute approximately 80,000,000 rational numbers with large numerators and denominators. It not too surprising that you ran out of memory. If machine precision reals are good enough, then you might try

Plus @@ (1/N @ Select[Range[10000000, 88888888], Not @ MemberQ[IntegerDigits[#], 9] &])


1.07145

% // FullForm

1.0714523172876622

-
This is incorrect. Opposite of what OP is asking for... –  rasher Mar 13 at 7:45
@rasher. Thanks for pointing out my error. I've fixed it. –  m_goldberg Mar 13 at 12:00

Here is a simple For loop that doesn't cost you any memory:

(x = 0.; For[i = 10000000, i <= 88888888, i++,
If[StringMatchQ[IntegerString[i], "*9*"] == False, x += 1./i]]; x)


You should get:

1.07145232

Edit

I initially wrote my answer to solve the memory problem, but I guess if speed is also an issue as it usually is with Mathematica one can compile my code easily by changing the predicate. So here is a compiled version:

f = Compile[{{x, _Integer}, {y, _Integer}},
Module[{sum = 0., i},
For[i = x, i <= y, i++, If[MemberQ[IntegerDigits[i], 9] == False, sum += Divide[1., i]]]; sum],
CompilationTarget -> "C"]


So

f[10000000, 88888888] // AbsoluteTiming


{10.618008, 1.07145232}

-

You can compute it in chunks, and then sum the values of the chunks. For example, something like

Total[1.0/Select[Range[k, k + chunk - 1], nonine[#] &]]

-