#### Got a credit card? use our Credit Card & Finance Calculators

Thanks to monabri,Dod101,Anonymous,Gersemi,robbelg, for Donating to support the site

cinelli
2 Lemon pips
Posts: 230
Joined: November 9th, 2016, 11:33 am
Has thanked: 60 times
Been thanked: 30 times

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?

Cinelli

UncleEbenezer
Lemon Quarter
Posts: 3694
Joined: November 4th, 2016, 8:17 pm
Has thanked: 422 times
Been thanked: 628 times

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.

Gengulphus
Lemon Quarter
Posts: 2968
Joined: November 4th, 2016, 1:17 am
Been thanked: 1523 times

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*10-9 = 111 when divided by 89, which is 24; the L=3 remainder is the remainder of 24*10-9 = 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 term-by-term 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

cinelli
2 Lemon pips
Posts: 230
Joined: November 9th, 2016, 11:33 am
Has thanked: 60 times
Been thanked: 30 times

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

Gengulphus
Lemon Quarter
Posts: 2968
Joined: November 4th, 2016, 1:17 am
Been thanked: 1523 times

Incidentally, the first few digits of the answer 11235... are the start of the well-known 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:

`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

UncleEbenezer
Lemon Quarter
Posts: 3694
Joined: November 4th, 2016, 8:17 pm
Has thanked: 422 times
Been thanked: 628 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 apparently-artificial 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 Fibonacci-like: 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?

UncleEbenezer
Lemon Quarter
Posts: 3694
Joined: November 4th, 2016, 8:17 pm
Has thanked: 422 times
Been thanked: 628 times

Replying to my own observation, googling "Fibonacci 89" tells us it's a well-known result.

Gengulphus
Lemon Quarter
Posts: 2968
Joined: November 4th, 2016, 1:17 am
Been thanked: 1523 times

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*10-9 = 111 when divided by 89, which is 24; the L=3 remainder is the remainder of 24*10-9 = 231 when divided by 89, which is 53, and so on. ...

... So the L=2 remainder is the remainder of 12*10-9 = 111 when divided by 89, which is 22; the L=3 remainder is the remainder of 22*10-9 = 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

jfgw
Lemon Slice
Posts: 953
Joined: November 4th, 2016, 3:36 pm
Has thanked: 146 times
Been thanked: 218 times

Spoiler
`.  112359550561797752809 * 99= 11123595505617977528091`

(The dot is to prevent the leading blanks from being stripped.)

Julian F. G. W.

Gengulphus
Lemon Quarter
Posts: 2968
Joined: November 4th, 2016, 1:17 am
Been thanked: 1523 times

UncleEbenezer wrote:Replying to my own observation, googling "Fibonacci 89" tells us it's a well-known 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(n-1) + F(n-2) 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 (100-10-1)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^2-B-1)". This arguably works out most spectacularly in binary, where B/(B^2-B-1) = 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

jfgw
Lemon Slice
Posts: 953
Joined: November 4th, 2016, 3:36 pm
Has thanked: 146 times
Been thanked: 218 times

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.