Puzzle time - integers

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