The answer is not what it seems

In the infinite series

1 9 + 1 99 + . . . . . . + 1 10 n 1 + \frac { 1 }{ 9 } +\frac { 1 }{ 99 } +......+\cfrac { 1 }{ { 10 }^{ n }-1 } + \ldots

at what place after the decimal point does the third 1 occur?

Note: The first 1 occurs at the first place after the decimal point.


Inspired by this problem


The answer is 944.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Ayush Garg
Jul 2, 2014

As you would have noticed

1 9 \frac { 1 }{ 9 } =0.11111......

1 99 \frac { 1 }{ 99 } =0.010101...

1 999 \frac { 1 }{ 999 } =0.001001001...

1 10 n 1 \cfrac { 1 }{ { 10 }^{ n }-1 } will have a one at every n t h { n }^{ th } position after decimal

So,every n t h { n }^{ th } place will have as many 1 as it has factors, if n+1 has factors between 0-9

So,for n having 11,21,31....... factors it will have 1 present at that position

Writing prime factorization we get

11=11*1

21=3*7

31=31*1

41=41*1

51=3*17........

Taking base 2 will generate the smallest number required.

So,smallest number with 11 factors is

n= 2 10 { 2 }^{ 10 } =1024>576

Similarly,

21 factors

n= 2 6 3 2 { 2 }^{ 6 }*{ 3 }^{ 2 } =576

31 factors

n= 2 30 { 2 }^{ 30 } >576

41 factors

n= 2 40 { 2 }^{40} >576

51 factors

n= 2 16 3 2 { 2 }^{ 16 }*{ 3 }^{ 2 } >576

So ,1 at second place occur at n = 576 \boxed{n=576}

However,if n has exactly 10,20,30...... factors and n+1 has factors in between 10 and 19 (both included) then also 1 will be present at that position

Writing prime factorization of 10 we get 10=2*5

So,we`ll have to check for numbers of the form 2 4 k { 2 }^{ 4}*k , 3 4 k { 3 }^{ 4}*k ....where k is a prime number other than the one it is multiplied with and so on till number is less than 1024

The smallest number satisfying above condition is given for n= 2 4 59 { 2 }^{ 4}*59 = 944 \boxed{944} ,it has exactly 10 factors and n+1 =945 has 16 factors

The last step of the solution is quite time taking so if any one has a better method please post it Please notify me about any typing mistakes since it was a long solution

This is my first attempt at publishing a problem so please like and reshare it if you liked the problem

Ayush Garg - 6 years, 11 months ago

What a solution truly amazing

Ronak Agarwal - 6 years, 11 months ago

it's amazing but i don't understand it completly. 1 occur at second you said at 576 but how diy you find 576, from where? and how to make sure it's the second?

the third look like more complicated. Where is 2.2.2.2.k from? and the 59 too :P

Hafizh Ahsan Permana - 6 years, 11 months ago

Log in to reply

If you read the condition for getting 1 it said either n has factors 11,21,31.... or simply n has 10 factors and it got 1 from carryover by n+1 smallest number having

11 factors is 1024

21 factors is 576

31 factors is 2 31 2^{31}

from here we are getting 576 at second place and 1024 at third place but another condition carryover is left

for carryover I said 10 factors (2*5) which would be present with numbers of form 2 4 3 2^{4} *3 , 2 4 5 2^{4} *5 , 2 4 7 2^{4} *7 ....... 3 4 2 3^{4} *2 , 3 4 5 3^{4} *5 ....... We have to check for all numbers which satisfy above criteria and the next number has 10-19 factors by trying all such numbers we arrive at the first number satisfying the condition which is 944<1024 2 4 59 2^{4} *59 =944

Ayush Garg - 6 years, 11 months ago

Question obtained attached with {1, 944, 576, 1024...} could make this happen.

Lu Chee Ket - 6 years, 9 months ago

This way for the last one is the easiest way to do. We can't exactly compare the factors of n n and n + 1 n+1 generally. Except that either, not both, n n or n + 1 n+1 have 2 k 2^{k} as a factor.

We have only 1 way to reduce our task by comparing 576 < 2 4 p . . . o r 3 4 p < 1024 576 < 2^{4}p ...or 3^{4}p < 1024 . If there're no such solutions k k , the answer will probably is 1024. There's only 8 numbers (37 to 61 for 2) and 1 number (11 for 3) to check.

Samuraiwarm Tsunayoshi - 6 years, 11 months ago

Did the complete same way bro!! :D

Aritra Jana - 6 years, 8 months ago

You're saying that "So,every n n 'th place will have as many 1 as it has factors, if n+1 has factors between 0-9". But what if n+1 has 9 factors and n+2 has more than 9 factors? The solution doesn't look completely rigorous.

mathh mathh - 6 years, 5 months ago

you're wrong, 608 has 11 factors, which are (1, 2, 4, 8, 16, 19, 32, 38, 76, 152, 608), and it has no carry effect since 609 only has 8 factors. (1, 3, 7, 21, 29, 87, 203, 609

Reinaldo Limantara - 6 years, 10 months ago

Log in to reply

You are missing 304 as a factor for 608.

Ronak Agarwal - 6 years, 9 months ago

Both 120 (1,2,3,4,5,6,8,10,12,15,20) and 168 (1,2,3,4,6,7,8,14,12,21,28) have 11 factors each, so shoudn't 168 be the answer?

Pranav Bhargav - 6 years, 10 months ago

Log in to reply

you are missing 30,60,120 as a factor of 120, and you are missing 168,84,56,42,24, as a factor of 168.

Ronak Agarwal - 6 years, 9 months ago
Lu Chee Ket
Aug 19, 2014

My computer program generates all the figures one by one.

For n and N:

T1(n) = Output(n MOD 1) {n >= 1}

T2(n) = Output(n MOD 2) {n>= 2}

T3(n) = Output(n MOD 3) {n>= 3}

T4(n) = Output(n MOD 4) {n >= 4}

...

TN(n) = Output(n MOD N) {n>= N}

Sn = T1(n) + T2(n) + .... + TN(n) {1<= N <=n}

IF n MOD N <> 0 THEN Output:=0 ELSE Output:=1; {To be realistic}

Decision onto "<>" is a potentially faster than "=". No better trick.

Example:

Chain 12 of more than enough for longer counts of guaranteed correctness:

 FOR nx:=1 TO 100011 DO
 BEGIN
      Sn:=0;
      FOR Ny:=1 TO nx DO
          IF nx>=Ny THEN
          BEGIN
             IF nx MOD Ny <> 0 THEN
                Output:=0
             ELSE
                 Output:=1;

             Sn:=Sn+Output
          END;

      {For next use only}
       S1[flip0]:=Sn;
       S2[flip0]:=S1[flip1];
       S3[flip0]:=S2[flip1];
       S4[flip0]:=S3[flip1];
       S5[flip0]:=S4[flip1];
       S6[flip0]:=S5[flip1];
       S7[flip0]:=S6[flip1];
       S8[flip0]:=S7[flip1];
       S9[flip0]:=S8[flip1];
      S10[flip0]:=S9[flip1];
      S11[flip0]:=S10[flip1];


      IF (((((((((((
          Sn DIV 10 +
          S1[flip1]) DIV 10 +  S2[flip1]) DIV 10 + S3[flip1]) DIV 10 +
          S4[flip1]) DIV 10 +  S5[flip1]) DIV 10 + S6[flip1]) DIV 10 +
          S7[flip1]) DIV 10 +  S8[flip1]) DIV 10 + S9[flip1]) DIV 10 +
         S10[flip1]) DIV 10 + S11[flip1])
                     MOD 10 = 1 THEN

          BEGIN
               INC(count);
               Found:=nx-11
          END
      ELSE
          Found:=0;

      IF Found<>0 THEN {Convenience to change}
      BEGIN
           WRITELN(S11[flip1]:3, '   ' , S10[flip1]:3, '   ' ,
                    S9[flip1]:3, '   '  , S8[flip1]:3, ' ...' ,
                    S1[flip1]:3, '   ' ,  Sn:3,
                   '   n= ', nx:5,
                   '   Count= ', count:4,
                   '   Found= ', Found);
      END;

      IF flip0=0 THEN
      BEGIN
           flip0:=1;
           flip1:=0
      END
      ELSE
      BEGIN
           flip0:=0;
           flip1:=1
      END
 END;
 WRITE('Count = ', count);

From 1 to 65535, there are 1003 counts of '1'. {1, 576, 944, 1024, 1424, 1600, 1616, 1875, 2015, 2349, 2375, 2384, 2511, 2672, 2916, 2960, 3059, 3136, 3184, 3248, 3311, 3483, 3824, 4304, 4779, 4784, ..., 64375, 64385, 64448, 64557, 64574, 64624, 64655, 64679, 64745, 64749, 64784, 64823, 64827, 64880, 64976, 65008, 65009, 65168, 65189, 65199, 65264, 65279, 65339, 65351, 65375 and 65456.} By WORD which is faster; border at 65535 checked with LONGINT. Only 3 term chain has been sufficient to be correct for this range. Checked with chain up to 12 terms and found agreed.

From 65535 to 100000, there are 726 counts of '1'. {65648, 65659, 65680, 65691, 65744, 65823, 65904, 66015, 66064, 66128, 66149, 66177, 66224, 66263, 66299, 66338, 66384, 66416, 66429, 66443, 66554, 66663, 66779, 66815, 66824, 66832, ..., 98739, 98747, 98768, 98783, 98903, 98999, 99014, 99024, 99056, 99152, 99197, 99245, 99344, 99375, 99383, 99395, 99440, 99449, 99539, 99664, 99665, 99728, 99755, 99827, 99899 and 99952.} By LONGINT which is slower. Only 4 term chain has been sufficient to be correct for this range. Checked with chain up to 12 terms and found agreed. 3 term chain surprisingly made 725 counts to total of 1728 counts!

There are a total of 1729 counts of '1' from 1st to 100,000th decimal place; 4 terms is the least required.

72333 [20, 8, 16, 40] 72336 as an only case found by a 4 terms instead of 12 terms above:

      IF
        ((((Sn DIV 10 +  S1[flip1]) DIV 10 +  S2[flip1]) DIV 10 + S3[flip1])
               MOD 10 = 1)

               AND NOT

        (((S1[flip1] DIV 10 +  S2[flip1]) DIV 10 +  S3[flip1]) MOD 10 = 1)

      THEN
          Found:=nx-3;

Other than '1', we can find all others.

943 [4] --> [5]

944 [10] --> [1]

945 [16?] --> [6]

{1, 576, 944, 1024...}

[29, 15, 58, 27, 36, 43, 72, 89, 15] and [5, 36, 40, 07, 39, 10, 02, 89, 13] are chain assumptions which need to be denied onto their validity. We overcome them here with long chain of up to 12, to count by not looking at their presence.

Lu Chee Ket - 6 years, 9 months ago

Log in to reply

Wow complete analysis of the question.

Ronak Agarwal - 6 years, 9 months ago

Log in to reply

Need to investigate features for more conclusions in a form of theorem. 1729 counts of '1' from 1 to 100000 is guaranteed to be a correct answer!

Lu Chee Ket - 6 years, 9 months ago

Obtaining 72333 [20, 8, 16, 40] 72336 for the missing count in 3 term checks only, for '1' from 1 to 100000 has been the most tedious challenge. Good or correct convention at programming is crucial. 72333 is the ONE. Find for '2', '3', '4'... '9' and '0' shall reveal the string. Just change MOD 10 = 1 to MOD 10 = 0 for example.

Lu Chee Ket - 6 years, 9 months ago

There are 5589 counts of '0' and the last one is at 99995th.

Lu Chee Ket - 6 years, 9 months ago

I caaaâãåä@àAÂÃÅÄÁ@ÀñÑtT

Kain Hakim - 2 years, 5 months ago

I used a computer program to count the numbers of factors including checking the number carried forward from the next number of factors.

Brute force: http://ideone.com/l0tRYO

ww margera - 6 years, 8 months ago

You think it's the most efficient way? (Just asking)

Akshay Krishna - 2 years, 6 months ago

Log in to reply

I doubt it is the most efficient way but it is the surest way.

Chew-Seong Cheong - 2 years, 6 months ago

Log in to reply

To ask if it's efficient is oxymoronic(I''m sorry). I should've asked: Why did you not write a proof this time. (Is there no direct proof?)

Akshay Krishna - 2 years, 6 months ago

Log in to reply

@Akshay Krishna I think it was a Python code. The result appeared in my screen. No proof, I just used the computer to check where the third 1 occurred.

Chew-Seong Cheong - 2 years, 6 months ago
Bert Seegmiller
Mar 14, 2018

After manually adding up the sequence and observing the resulting fraction, I figured that the manual method would be prone to errors. Unix provides an arbitrary-precision command-line calculator program called "bc". I wrote the following script and examined the output.

1
2
3
4
5
6
7
8
9
scale=1000;
frac=0;
lastpow=0;
for ( i=1; i<1000; i++) {
   newpow=lastpow*10+9;
   frac += 1/newpow;
   lastpow=newpow;
   frac;
}

Looking at the results in a text editor gave me the answer. I wish I had the maths to solve it more analytically via formulae. It was luck I picked 1000 iterations, to find it at the 944th iteration.

0.1223242434262445262644283446282644492448282664303646284844322467482648322466483054324448324644522669282884322850284664563446522848324488283244554466322868522452502684363866287044382848484688342489323244524470562644564452483294322888324648402666684848384489285264364846363084722476282688583846324884584450523248362526285448556448562664602652524884323292284684443472483068522888563244368466365244582495284708562846525248442468684688402886483698324454384644962492363084384848487264444489522852324930483244444866365084524856322724603872484844842452562672564486326084324508363248812652484924384850368648442866683288582496283284605486642844526876283288405286285068442488924648642529285648384850562724564458365484522868568644504646723678522532523288364472563048642496284724583646326884644895482648644486365864528848403248604532282928382854685284523446727052522928363284444472564868922460383284364906485684674888482676404486563644646472366645042852285168325256324684683866563288384530285864364892643248522496

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...