Puzzle time - integers

Klaus

:::

Obviously, when a number n is in S, then n+5 must also be in S.

So once we have all digits from 0 to 4 (or 5 to 9) as last digits of numbers, all numbers above it must be in S.

So the question is whether we ever get all last digits.

I think we can get to all last-digits except 0 and 5, since any number that ends with 0 or 5 squared also ends with 0 or 5.

So, my theory about the positive integers not in S is:

There's some noise in the beginning, and after a while it's only the numbers that end with 0 or 5.

:::

jon-nyc

:::

On the right track but not quite there

:::

Klaus

So you are saying my last statement is wrong, or are you saying it's not precise enough?

jon-nyc

Depends on how one defines ‘noise‘. But what I really mean is “from what I infer from your words you’re still missing an insight here”

Klaus

OK, here's a precise version of the statement:

:::

There is a number N, such that for all n >N, n is not in S if and only if the last digit of n is 0 or 5.

:::

Is that correct?

jon-nyc

Yes but tell me N. You’re missing something or you would know what N is.

Klaus

N is smaller than or equal to 2915. Now don't tell me you want me to worry about selecting a particular number between 1 and 2915!!!

jon-nyc

Yes I do.

jon-nyc

What Klaus missed:

:::

The only ‘noise’ (besides all multiples of 5) is the number 1.

2 is granted which gets you all numbers ending in 2 or 7.
7^2 is 49 which gets you all the numbers ending in 9 and 4 above that
after 49 is 54. 54^2 is 3136 which gets you all the numbers ending in 6 or 1 above it.
BUT
once you have the *6s, you’ll get to 6^8 which gets you back to 6 and 11, etc.
that gets you to 16 which gets you back to 4 and 9
that 9 gets you back to 3 and 8

So we have 2,3,4,6,7,8,9 covered plus any number that is a multiple of 5 above them.

So only 1 is missing, along with all multiples of 5

:::

Klaus

Nice!

54^2 is 2916 and not 3136, though - that was the source of the 2915 bound I was giving above. So my bound was pointing in the right direction

jon-nyc

My math buddy at CS pointed out that Fermat’s Little Theorem could help here too rather than finding actual paths back to the lower numbers.

The New Coffee Room