In the infinite series
9 1 + 9 9 1 + . . . . . . + 1 0 n − 1 1 + …
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
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.
This is my first attempt at publishing a problem so please like and reshare it if you liked the problem
What a solution truly amazing
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
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 3 1
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 ∗ 5 , 2 4 ∗ 7 ....... 3 4 ∗ 2 , 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 ∗ 5 9 =944
Question obtained attached with {1, 944, 576, 1024...} could make this happen.
This way for the last one is the easiest way to do. We can't exactly compare the factors of n and n + 1 generally. Except that either, not both, n or n + 1 have 2 k as a factor.
We have only 1 way to reduce our task by comparing 5 7 6 < 2 4 p . . . o r 3 4 p < 1 0 2 4 . If there're no such solutions 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.
Did the complete same way bro!! :D
You're saying that "So,every 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.
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
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?
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.
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.
Log in to reply
Wow complete analysis of the question.
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!
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.
There are 5589 counts of '0' and the last one is at 99995th.
I caaaâãåä@àAÂÃÅÄÁ@ÀñÑtT
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
You think it's the most efficient way? (Just asking)
Log in to reply
I doubt it is the most efficient way but it is the surest way.
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?)
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.
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 |
|
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
Problem Loading...
Note Loading...
Set Loading...
As you would have noticed
9 1 =0.11111......
9 9 1 =0.010101...
9 9 9 1 =0.001001001...
1 0 n − 1 1 will have a one at every n t h position after decimal
So,every n t h 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 1 0 =1024>576
Similarly,
21 factors
n= 2 6 ∗ 3 2 =576
31 factors
n= 2 3 0 >576
41 factors
n= 2 4 0 >576
51 factors
n= 2 1 6 ∗ 3 2 >576
So ,1 at second place occur at n = 5 7 6
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 , 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 ∗ 5 9 = 9 4 4 ,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