Puzzle time - integers
-
wrote on 20 Jul 2020, 09:36 last edited by 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?
-
wrote on 20 Jul 2020, 09:50 last edited by
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?
-
wrote on 20 Jul 2020, 09:51 last edited by
I considered adding the word smallest and thought ‘no one here will be such a putz to pretend not to understand’
-
wrote on 20 Jul 2020, 09:54 last edited by
I'm happy to help
There are many such definitions where you want something different from "smallest" (e.g. coinductive definitions).
-
wrote on 20 Jul 2020, 09:58 last edited by Klaus
1 is not in S.
(note that you didn't ask for an exhaustive list of those not in S
) -
wrote on 20 Jul 2020, 10:02 last edited by
...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?
-
wrote on 20 Jul 2020, 10:06 last edited by
Ha
-
wrote on 20 Jul 2020, 11:27 last edited by 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.
:::
-
wrote on 20 Jul 2020, 11:29 last edited by
:::
On the right track but not quite there
:::
-
wrote on 20 Jul 2020, 11:32 last edited by
So you are saying my last statement is wrong, or are you saying it's not precise enough?
-
wrote on 20 Jul 2020, 11:37 last edited by
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”
-
wrote on 20 Jul 2020, 11:59 last edited by
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?
-
wrote on 20 Jul 2020, 12:02 last edited by jon-nyc
Yes but tell me N. You’re missing something or you would know what N is.
-
wrote on 20 Jul 2020, 12:10 last edited by 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!!!
-
wrote on 20 Jul 2020, 13:10 last edited by
Yes I do.
-
wrote on 20 Jul 2020, 18:14 last edited by
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
:::
-
wrote on 20 Jul 2020, 20:52 last edited by
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
-
wrote on 20 Jul 2020, 20:58 last edited by
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.