Got a credit card? use our Credit Card & Finance Calculators
Thanks to 88V8,Howard,Bhoddhisatva,penym,Anonymous, for Donating to support the site
Adding

 Lemon Quarter
 Posts: 4321
 Joined: November 4th, 2016, 8:17 pm
 Has thanked: 495 times
 Been thanked: 757 times
Re: Adding
Easier than your usual, methinks. We can work inductively from the left to find sequences of digits such that seq x 99 <= 1.seq.1 < seq x 100. Furthermore, elementary properties of decimal numbers tell us the last digit is a 9. We have some other properties (like that the sum of the digits is 7 + some multiple of 9) which might've been useful if I'd had to program it, but that wasn't necessary.
Just working inductively from the left, we get 112359550561797752809.
Just working inductively from the left, we get 112359550561797752809.

 Lemon Quarter
 Posts: 3101
 Joined: November 4th, 2016, 1:17 am
 Been thanked: 1609 times
Re: Adding
cinelli wrote:What is the smallest positive integer with the property that when the digit 1 is appended to both ends, the new number is 99 times the original?
Spoiler...
I.e. find the smallest integer N such that 10^(L+1) + 10N + 1 = 99N, where L is the length of N written in decimal. That implies that 10^(L+1) + 1 = 89N, so L needs to be such that 10^(L+1) + 1 is divisible by 89, and we need to find the smallest such L. We also need in principle to check that L is indeed the length of (10^(L+1) + 1) / 89, but 10^(L+1) + 1 has length L+2 and its first two digits are 10, so dividing it by 89 will reduce its length by 2 to L, so that's automatically true.
To mostly avoid potentially having to work with very big numbers, observe that 1001 = 10*101  9, 10001 = 10*1001  9, 100001 = 10*10001  9, etc. So I can work out the remainders when 101, 1001, 10001, 100001, ... are divided by 89 by starting with 12 (the remainder of 101 when divided by 89), and then work out each remainder by taking the previous one, multiplying by 10, subtracting 9 and dividing by 89 to get the remainder. So the L=2 remainder is the remainder of 12*109 = 111 when divided by 89, which is 24; the L=3 remainder is the remainder of 24*109 = 231 when divided by 89, which is 53, and so on. That sequence goes 12, 22, 33, 54, 86, 50, 46, 6, 51, 56, 17, 72, 88, 70, 68, 48, 26, 73, 9, 81, 0, ... We can stop there, as we've now reached the first term with remainder 0 when divided by 89, i.e. which is divisible by 89. Counting the terms, it is the L=21 remainder, so the answer to the puzzle is that N = 10,000,000,000,000,000,000,001/89 = 112,359,550,561,797,752,809.
Another way of looking at this is that the answer is slightly more than the decimal places of 1/89th, and that if one calculates 1/89 by long division, you reach the correct "slightly more" point when you get to the point of having a remainder of 88, so that if the dividend digit had been 1 at that point rather than 0, the remainder would have been 0 and the quotient would be 1 greater. That long division starts:
.
0.01123595...
...
89 / 1.00000000...
89

110
89

210
178

320
267

530
445

850
801

490
445

450
...
The connection is that the sequence 11, 21, 32, 53, 85, 49, 45, ... of partial remainders is termbyterm one less than the sequence of remainders I worked out above, except that when the former reaches 88, the latter is 0. In either case, we have reached the answer apart from the former needing to adjust the quotient from the division up by 1 in that place and ignore the rest of it.
I'll add that I believe the inductive working that UncleEbenezer describes in his answer (which I only looked at after producing mine) is essentially this long division.
Gengulphus

 Lemon Slice
 Posts: 273
 Joined: November 9th, 2016, 11:33 am
 Has thanked: 75 times
 Been thanked: 47 times
Re: Adding
Well solved, both. It is very pleasing that two methods emerged. My own method was to write the equation
99*n = 10^x + 10*n + 1
which becomes
89*n = 10^x +1
and the RHS is of the form 1000...0001. Then find the smallest n by brute force, whereas Gengulphus has an elegant system.
Cinelli
99*n = 10^x + 10*n + 1
which becomes
89*n = 10^x +1
and the RHS is of the form 1000...0001. Then find the smallest n by brute force, whereas Gengulphus has an elegant system.
Cinelli

 Lemon Quarter
 Posts: 3101
 Joined: November 4th, 2016, 1:17 am
 Been thanked: 1609 times
Re: Adding
Incidentally, the first few digits of the answer 11235... are the start of the wellknown Fibonacci sequence 1, 1, 2, 3, 5, ... That doesn't continue, as the next digit is 9 and the next number in the Fibonacci sequence is 8  except that if I take the next two numbers 8, 13 of the Fibonacci sequence and regard the 1 from the 13 as overflowing into the column to its left, which already contains 8, I get 9... And looking similarly at say the first 15 elements of the Fibonacci sequence, adding them up similarly, I get:
and I've now got the first 12 digits of the answer...
So the questions I'll pose people are: Is this just coincidence, and if not, what lies behind it? Does it actually continue indefinitely, and if not, where does it come to an end?
Gengulphus
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
 +
112359550561680
and I've now got the first 12 digits of the answer...
So the questions I'll pose people are: Is this just coincidence, and if not, what lies behind it? Does it actually continue indefinitely, and if not, where does it come to an end?
Gengulphus

 Lemon Quarter
 Posts: 4321
 Joined: November 4th, 2016, 8:17 pm
 Has thanked: 495 times
 Been thanked: 757 times
Re: Fibbs
Hmmm. Most intriguing.
It obviously can't continue indefinitely, because the number doesn't. And it would seem remarkable indeed if such an apparentlyartificial construct arose out of something so natural.
On the other hand, Gengulphus's solution brought us a sequence of remainders from dividing by 89: 12, 22, 33, 54, 86, 50, 46, 6, 51, 56, 17, 72, 88, 70, 68, 48, 26, 73, 9, 81, 0. That looks a bit Fibonaccilike: add any two, and the next is one less than their sum modulo 89 (and that one is of course the 1 appended to the numerator in the original problem  if we take 100/89, 1000/89, ... it falls out).
Following that line of investigation, just look at 1/89. A strangely familiar sequence of digits ( 1123595505617977528089887640449438202247191011235955056179775280898876404494382022471910112359550...), and surely the key to your solution. We seem to have reduced it to a property of dividing by 89.
Further wild thought: do any similar properties arise if we pose the problem in numbers to a base other than 10?
It obviously can't continue indefinitely, because the number doesn't. And it would seem remarkable indeed if such an apparentlyartificial construct arose out of something so natural.
On the other hand, Gengulphus's solution brought us a sequence of remainders from dividing by 89: 12, 22, 33, 54, 86, 50, 46, 6, 51, 56, 17, 72, 88, 70, 68, 48, 26, 73, 9, 81, 0. That looks a bit Fibonaccilike: add any two, and the next is one less than their sum modulo 89 (and that one is of course the 1 appended to the numerator in the original problem  if we take 100/89, 1000/89, ... it falls out).
Following that line of investigation, just look at 1/89. A strangely familiar sequence of digits ( 1123595505617977528089887640449438202247191011235955056179775280898876404494382022471910112359550...), and surely the key to your solution. We seem to have reduced it to a property of dividing by 89.
Further wild thought: do any similar properties arise if we pose the problem in numbers to a base other than 10?

 Lemon Quarter
 Posts: 4321
 Joined: November 4th, 2016, 8:17 pm
 Has thanked: 495 times
 Been thanked: 757 times
Re: Adding
Replying to my own observation, googling "Fibonacci 89" tells us it's a wellknown result.

 Lemon Quarter
 Posts: 3101
 Joined: November 4th, 2016, 1:17 am
 Been thanked: 1609 times
Re: Adding
Gengulphus wrote:cinelli wrote:What is the smallest positive integer with the property that when the digit 1 is appended to both ends, the new number is 99 times the original?
I've noticed an uncorrected arithmetic mistake in my spoiler  the sentence:
... So the L=2 remainder is the remainder of 12*109 = 111 when divided by 89, which is 24; the L=3 remainder is the remainder of 24*109 = 231 when divided by 89, which is 53, and so on. ...
should read:
... So the L=2 remainder is the remainder of 12*109 = 111 when divided by 89, which is 22; the L=3 remainder is the remainder of 22*109 = 211 when divided by 89, which is 33, and so on. ...
I did actually detect the error while I was writing the post, and mostly corrected it  but that sentence escaped the net! Apologies to anyone who found it a bit confusing...
Gengulphus

 Lemon Quarter
 Posts: 1073
 Joined: November 4th, 2016, 3:36 pm
 Has thanked: 174 times
 Been thanked: 258 times
Re: Adding
Spoiler
(The dot is to prevent the leading blanks from being stripped.)
Julian F. G. W.
. 112359550561797752809 * 99
= 11123595505617977528091
(The dot is to prevent the leading blanks from being stripped.)
Julian F. G. W.

 Lemon Quarter
 Posts: 3101
 Joined: November 4th, 2016, 1:17 am
 Been thanked: 1609 times
Re: Adding
UncleEbenezer wrote:Replying to my own observation, googling "Fibonacci 89" tells us it's a wellknown result.
Yes, indeed  I try not to post research problems to this board, or at least to warn people upfront that the problem doesn't have a known answer if I do post one!
Some of the answers I've seen from that bit of googling are a bit cumbersome, with lots of matrix equations, etc, that may make people's eyes glaze over  and it is in fact pretty straightforward. Basically, if one starts the Fibonacci sequence with F(1) = 1, F(2) = 1 and then continues it with F(n) = F(n1) + F(n2) for all n >= 3, the addition of the Fibonacci numbers that I gave is calculating the following sum:
X = F(1)/10 + F(2)/100 + F(3)/1000 + F(4)/10000 + F(5)/100000 + ...
Now use the defining equations of the Fibonacci sequence on this sum:
F(1)/10 = 1/10
F(2)/100 = 1/100
F(3)/1000 = F(1)/1000 + F(2)/1000
F(4)/10000 = F(2)/10000 + F(3)/10000
F(5)/100000 = F(3)/100000 + F(4)/100000
...
Add up all the first parts of those sums and then all the second parts, and we see that:
X = 1/10 + 1/100
+ F(1)/1000 + F(2)/10000 + F(3)/100000 + ...
+ F(2)/1000 + F(3)/10000 + F(4)/100000 + ...
But look at the second line of that addition as I've now written it out, and it's clearly just X divided by 100. And similarly, the third line is X minus its first term F(1)/10 = 1/10, all divided by 10, i.e. X/10  1/100. So:
X = 1/10 + 1/100 + X/100 + X/10  1/100
= 1/10 + X/100 + X/10
Multiplying through by 100 gives 100X = 10 + X + 10X, then collecting together the X's gives (100101)X = 10, so 89X = 10, i.e. X = 10/89. So I get the decimal places of 10/89, which are of course the decimal places of 1/89 excluding the initial 0.
It's quite easy to adapt that argument for any base B other than 10  basically just put Bs in place of the 10s, B^2s in place of the 100s, B^3s in place of the 1000s, B^4s in place of the 10000s, etc. So the answer to UncleEbenezer's "Further wild thought: do any similar properties arise if we pose the problem in numbers to a base other than 10?" is "yes  in base B, the sum is related to the decimal places of B/(B^2B1)". This arguably works out most spectacularly in binary, where B/(B^2B1) = 2. The finite sums do converge to 2 from below, so they're of the form 1.111... with more and more consecutive 1s, but the number of consecutive 1s rises quite slowly compared with the number of digits in the addition result. E.g. you'd have to go quite a bit further than the analogue of the addition of the first 15 terms that I did earlier:
.
1
1
10
11
101
1000
1101
10101
100010
110111
1011001
10010000
11101001
101111001
1001100010
 +
1111010111101000
before the fact that the sums were starting with more and more consecutive 1s really became all that noticeable...
Gengulphus

 Lemon Quarter
 Posts: 1073
 Joined: November 4th, 2016, 3:36 pm
 Has thanked: 174 times
 Been thanked: 258 times
Re: Adding
Looking at the spoilers, I see that UncleEbenezer got the correct answer quite quickly working in the opposite direction to how I did it.
My method:
After working out that 1 followed by the same number of 0s as the length of the number we were looking for followed by another 1 was divisible by 89, it was easy.
The last digit of 100...001 is a 1 so the units digit of the number we are looking for multiplied by 89 (or just 9) must end in 1. The only possiblity is 9.
9*89=801 so the tens digit multiplied by 89, when added to 0, must end in a 0. The tens digit is, therefore a 0.
The hundreds digit multiplied by 89, when added to 8, must end in 0. The hundreds digit is, therefore, 8.
Keep doing this until you get a 1 followed by zeros and then a 1.
9*89=801
09*89=801
809*89=72001
2809*89=250001
52809*89=4700001
And so on.
The next number to have this property is 11235955056179775280898876404494382022471910112359550561797752809.
Clearly, you can prefix this with 11235955056179775280898876404494382022471910 repeatedly to get higher numbers with this property.
Julian F. G. W.
My method:
After working out that 1 followed by the same number of 0s as the length of the number we were looking for followed by another 1 was divisible by 89, it was easy.
The last digit of 100...001 is a 1 so the units digit of the number we are looking for multiplied by 89 (or just 9) must end in 1. The only possiblity is 9.
9*89=801 so the tens digit multiplied by 89, when added to 0, must end in a 0. The tens digit is, therefore a 0.
The hundreds digit multiplied by 89, when added to 8, must end in 0. The hundreds digit is, therefore, 8.
Keep doing this until you get a 1 followed by zeros and then a 1.
9*89=801
09*89=801
809*89=72001
2809*89=250001
52809*89=4700001
And so on.
The next number to have this property is 11235955056179775280898876404494382022471910112359550561797752809.
Clearly, you can prefix this with 11235955056179775280898876404494382022471910 repeatedly to get higher numbers with this property.
Julian F. G. W.
Return to “Games, Puzzles and Riddles”
Who is online
Users browsing this forum: No registered users and 1 guest