A positive integer less than 30 million is such that if we subtract 5 from it – the resulting number is divisible by 8.
At the first step, from the number (considered originally) diminished by 5 - we subtract the eighth part. We then obtain a number that also becomes divisible by 8 after 5 is subtracted from it.
At the second step, we derive another in the same way, namely by subtracting a eighth part from the number at the end of the first step diminished by 5. The resulting number is also divisible by 8 after subtracting 5.
The operation concludes at 8th step given that at the end of 7th step we get a number that is divisible by 8 after after subtracting 5.
Determine the positive integer initially before the first step.
*** The resulting number at the end of 8th step is NOT necessarily divisible by 8 after subtracting 5.
Final answer:
16777181
The final step is to reduce a number that is divisible by 8 by 1/8. The final result must be divisible by 7.
Do the process in reverse starting with a number divisible by 7.
First multiply by 8/7 then add 5. This result must by divisible by 7 in order to continue.
Try 28. 28 --> 32 --> 37 no, not divisible by 7.
I ran a program to repeat this process and record the first instance of the number of repetitions while still ending with a number divisible by 7.
Using this reverse process, the final integer result will be (ignoring the +5 steps) approximately (starting number) * (8/7)^i where i is the number of repetitions.
(8/7)^8 is about 2.9, so if the process survives 8 repetitions, the starting number (of the reverse process) will need to be less than about 10 million for the end result to be less than 30 million. The answer was found at about 5.7 million.
Output of my program is left of the arrow, corresponding solution (for a given number of repetitions of the reverse algorithm) added manually to the right of the arrow:
1 14 --> 29
2 308 --> 477
3 2366 --> 4061
4 16772 --> 32733
5 117614 --> 262109
6 823508 --> 2097117
7 5764766 --> 16777181
When I used a spreadsheet to run the process forward, I realized I was undercounting the repetitions by 1, so the last line above is actually 8 repetitions, which is fortunate because I did not find a result with my program for one more repetition even by going up to 10 Billion.
rep N N-5 (N-5)*7/8
1 16777181 16777176 14680029
2 14680029 14680024 12845021
3 12845021 12845016 11239389
4 11239389 11239384 9834461
5 9834461 9834456 8605149
6 8605149 8605144 7529501
7 7529501 7529496 6588309
8 6588309 6588304 5764766
-------------
#reverse process
def f(n):
return n*8/7 + 5
maxi = 0
maxistart = 0
maxn = 0
beststart = 0
for start in range(0,10000000000, 7):
n = start
for i in range(8):
if i > maxi:
maxi = i
maxistart = start
print(i,start)
n = f(n)
if n > maxn:
maxn = n
beststart = start
if n%7 != 0:
break
print (maxn, beststart, maxi, maxistart)
|
|
Posted by Larry
on 2023-11-06 10:07:52 |
Solution
