Puzzle time - integers

[Klaus]

...and if you want the complete set:

It's the set of positive integers minus S.

Which is a perfectly valid mathematical definition of the integers not in S.

So presumably you want us to specify that set in a particular way?

[jon-nyc]

Ha

[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.