Puzzle time - integers

[jon-nyc]

S is the set of positive integers such that:

2 is in S,

n is in S whenever n^2 is in S,

(n+5)^2 is in S whenever n is in S.

Which positive integers are not in S?

[Klaus]

None of the conditions you specify says something about numbers not in S, so there's no way to say something about numbers not in S.

Presumably you meant to say that S is the smallest set that is closed under the application of these rules?

[jon-nyc]

I considered adding the word smallest and thought ‘no one here will be such a putz to pretend not to understand’

[Klaus]

I'm happy to help

There are many such definitions where you want something different from "smallest" (e.g. coinductive definitions).

[Klaus]

1 is not in S.

(note that you didn't ask for an exhaustive list of those not in S )

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