Extension to A056100
62 views
Skip to first unread message
Michel Marcus
Aug 5, 2025, 8:27:05 AMAug 5
to seq...@googlegroups.com
Hi all,
One can search for the least k such that A056100(k) is n.
I have used -n if no such k below 10^9.
I got: 6, -2, 4, 33, 8, 145, 9, 37063859, 16, 51, 26, 1441, 15, 2353, 34, 69, 20, -18, 27, 7201, 25, 87, 115, 9911837, 56, 385, 58, 45, 62, 86125529, 57, 30721, 35, 123, 74, 295, 90, -38, 82, 141, 86, 70561, 49, 77857739, 94, 159, 329, 34884199, 60, 679, 106, 177, 517582, 151633, 78, ...
Can we find a(2), a(18), a(38), a(72) , a(80) ?
Best.
MM
Neil Sloane
Aug 5, 2025, 9:24:46 AMAug 5
to seq...@googlegroups.com
Interesting question!
If you look at the first time you get 2*n+1, you get (this is a bisection of your list):
6, 4, 8, 9, 16, 26, 15, 34, 20, 27, 25, 115, 56, 58, 62, 57, 35, 74, 90, 82, 86, 49, 94, 329, 60, 106, 517582, 78, 91, 122, 110, 77, 128, 111, 142, 146, 88, 427, 158, 102, 100, 265, 273, 178, 242, 95, 212, 194, 104, 202, 125, 462, 214, 218, 132, 121, 344, 138, 470, 241582, 268, 365, 254, 153, 256, 338, 292, 274, 278, 210, 143, 415, 312, 209, 302, 174, 187, 314, 169, 721, 272, 186, 334, 170, 182, 346, 803, 651, 358, 362, 387, 515, 488, 291, 382, 386, 228, 394, 398, 207, 299, 565, 436, 221, 304, 225, 247, 917, 255, 2509, 305, 246, 352, 458, 434, 466, 584, 258, 266, 482, 280, 817, 511, 381, 502, 725, 308, 514, 320, 282, 355, ...
I think that sequence should be in the OEIS - could you add it?
Best regards
Neil
Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njas...@gmail.com
--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAFxT7zVm_-Y2MD-4%2B5MRPt6x7P60tUV16iuCUwrFRSKm-M9F8w%40mail.gmail.com.
Michel Marcus
Aug 5, 2025, 12:56:31 PMAug 5
to seq...@googlegroups.com
I submitted A386856.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAAOnSgSZ7dw%2BiQJYu1usZjDXmPHUbak13QjESgbhzgjYpwS_Hg%40mail.gmail.com.
Neil Sloane
Aug 5, 2025, 1:53:15 PMAug 5
to seq...@googlegroups.com
Maybe add "or -1 if no such k exists" ? Or if you have a proof, give a sketch of the proof.
Best regards
Neil
Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njas...@gmail.com
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAFxT7zV6JicMaZBB7bWEcF7ZhtbmO8BLTVThawD8CMD-EdFbCA%40mail.gmail.com.
Neil Sloane
Aug 5, 2025, 3:10:02 PMAug 5
to seq...@googlegroups.com
I forwarded Michel's question to the Math Fun list. Two answers have come in so far:
(1) From Gareth McCaughan
(start)
The function n -> phi(n) sigma(n) is a multiplicative function. It's
value at p^k is p^(k-1) (p-1) . (p^(k+1)-1)/(p-1) = p^(k-1) (p^(k+1)-1).
When k>1 this is a multiple of p; so if p^2|n then phi(n) sigma(n) is a
multiple of p and hence can't be 1 mod n.
So suppose n is a product if distinct primes p; then phi(n) sigma(n) =
product (p^2-1).
If in fact n is prime then this is just n^2-1 which isn't 1 mod n, so n
is a product of _multiple_ distinct primes.
If n = pq then we have pq | (p^2-1)(q^2-1)-1 = p^2 q^2 - p^2 - q^2 so p
| q^2, impossible, so n is the product of _at least three_ distinct primes.
At least one of the p^2-1 factors is even, so an even number is 1 mod n,
so n is odd, so n is the product of at least three distinct odd primes.
We can't let product (p^2-1) be a multiple of any of the primes, so none
of our primes is +-1 mod any of the others.
At this point I run out of obvious things to say; perhaps the conditions
above are enough to make it fairly unsurprising for there to be no
smallish solutions even if there are some not-so-small ones?
Assuming my stupid code to check this doesn't have bugs, there are no
such n that are products of at most 5 odd primes below 1000. That does
feel like a bit too much of a coincidence if there's nothing going on
besides the conditions listed above, so probably there is. I'm not
currently seeing what, though.
value at p^k is p^(k-1) (p-1) . (p^(k+1)-1)/(p-1) = p^(k-1) (p^(k+1)-1).
When k>1 this is a multiple of p; so if p^2|n then phi(n) sigma(n) is a
multiple of p and hence can't be 1 mod n.
So suppose n is a product if distinct primes p; then phi(n) sigma(n) =
product (p^2-1).
If in fact n is prime then this is just n^2-1 which isn't 1 mod n, so n
is a product of _multiple_ distinct primes.
If n = pq then we have pq | (p^2-1)(q^2-1)-1 = p^2 q^2 - p^2 - q^2 so p
| q^2, impossible, so n is the product of _at least three_ distinct primes.
At least one of the p^2-1 factors is even, so an even number is 1 mod n,
so n is odd, so n is the product of at least three distinct odd primes.
We can't let product (p^2-1) be a multiple of any of the primes, so none
of our primes is +-1 mod any of the others.
At this point I run out of obvious things to say; perhaps the conditions
above are enough to make it fairly unsurprising for there to be no
smallish solutions even if there are some not-so-small ones?
Assuming my stupid code to check this doesn't have bugs, there are no
such n that are products of at most 5 odd primes below 1000. That does
feel like a bit too much of a coincidence if there's nothing going on
besides the conditions listed above, so probably there is. I'm not
currently seeing what, though.
(end)
(2) From Tomas Rokicki
Best regards
Neil
Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njas...@gmail.com
Reply all
Reply to author
Forward
0 new messages