mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Computer Science & Computational Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=116)
-   -   Need more items for sequence 17, 257, 641, 65537, … (https://www.mersenneforum.org/showthread.php?t=24855)

 miket 2019-10-17 01:17

Need more items for sequence 17, 257, 641, 65537, …

Let n be an odd positive integer, Let o=ordn2 be the order of 2 modulo n and m the period of 1/n, k is number of distinct odd residues contained in set {2^1,2^2,...,2^{n−1}} modulo n.

If odd part of o,m and k is 1 and k divide n-1, then n is item in the sequence 17, 257, 641, 65537, ….

167772161 also is item.It seems all known items in the sequence are Fermat factors and divide 2^(2^100) - 1 and 10^(10^100) - 1.

Here's my PARI/GP code to check numbers(there's large space left for improve):

[CODE] oddres(n)=if(n<2,0,n>>valuation(n,2))
ck(n) = {
my(l=List(),m=if(1<n/=5^valuation(n, 5)<<valuation(n, 2), znorder(Mod(10, n)), 0),o=znorder(Mod(2,n)));
forstep(i=0,-o,-1,if((2^i % n) % 2 == 1, listput(l, 2^i % n)));
[m,#(Set(l)),o]
}
forstep(n=1, 1e3, 2, [m,k,o] = ck(n); if( oddres(m) == 1 && (n - 1) % m == 0 && oddres(k) == 1 && oddres(o) == 1, print1(n", "m", "k", "o",\n")))
\\out put:
17, 16, 4, 8,
257, 256, 8, 16,
641, 32, 32, 64,[/CODE]

and Python code to get the o, k

[CODE] def ck(n):
def f(n, t):
k = 0
while (t << k) < n: k += 1
return (t << k) - n, k
v, k, o = 1, 0, 0
while True:
v, z = f(n, v)
k += z
o = o + 1
if v == 1 or v == 0: break
return o, k

ck(17)
# out put (4, 8)[/CODE]

Are there more efficient way to calculate k(number of distinct odd residues contained in set {2^1,2^2,...,2^{n−1}} modulo n)?

 Dr Sardonicus 2019-10-17 15:03

[QUOTE=miket;528190]Let n be an odd positive integer, Let o=ordn2 be the order of 2 modulo n and m the period of 1/n, k is number of distinct odd residues contained in set {2^1,2^2,...,2^{n−1}} modulo n.

If odd part of o,m and k is 1 and k divide n-1, then n is item in the sequence 17, 257, 641, 65537, ….
<snip>[/QUOTE]
First, I don't understand why n = 3 isn't on the list.

Second, the "period" of 1/n apparently is to the base ten. If this period is a power of 2, then the multiplicative order of 10 (ten) (mod n) must also be a power of 2 (so 5 can not divide n), and the multiplicative order of 5 (mod n) must therefore also be a power of 2. The multiplicative orders may, of course, be [i]different[/i] powers of 2.

Third, if n is [i]prime[/i], and the multiplicative order o > 1 of 2 (mod n) is even, then exactly half the representatives of {1, 2, ... 2^(o-1) (mod n)} in the interval [1,n-1] -- that is, o/2 of them -- are odd. I leave the proof as an exercise for the reader.

 Dr Sardonicus 2019-10-17 19:41

Inspired by the examples p = 5*2^7 + 1 = 641 and p = 5*2^25 + 1 = 167772161 already given, I tried other known prime factors 5*2^k + 1 of Fermat numbers.

Numerical checking showed that the multiplicative orders of 5 (mod p) for p = 5*2^39 + 1, 5*2^75 + 1, 5*2^127 + 1, 5*2^1947 + 1, and 5*2^3313 + 1 are powers of 2.

I did not attempt a numerical check for p = 5*2^23473 + 1, a factor of F[sub]23471[/sub]

It is, alas, not always true that 5 is a quintic residue of p = 5*2^k + 1, which is what is needed to make the multiplicative order of 5 (mod p) a power of 2 when p = 5*2^k + 1.

The primes p = 11 = 5*2^1 + 1, 41 = 5*2^3 + 1, and 40961 = 5*2^13 + 1 provide counterexamples.

I am sure there are known criteria for when 5 is a quintic residue (mod p), but I am too lazy to look them up.

It is possible (AFAIK) that the multiplicative order of 5 (mod p) is a power of 2 for other prime factors k*2^n + 1 (k odd), of composite Fermat numbers, but, apart from the known prime factors of Fermat numbers up to F[sub]23[/sub], I haven't checked them.

 miket 2019-10-18 06:09

[QUOTE=Dr Sardonicus;528214]First, I don't understand why n = 3 isn't on the list.
[/QUOTE]

'If odd part of o,m and k is 1 and k divide n-1' should be: 'If o,m and k in the set {2,4,8,...} and k divide n-1'.

 Dr Sardonicus 2019-10-19 12:16

I checked p = 5*2^23473 + 1; it didn't take nearly as long as I had feared it would. It's on the list.

 Dr Sardonicus 2019-10-21 20:20

This topic inspired me to formulate a hypothesis.

I checked some of the primes p = q*2^n + 1 which divide F[sub]m[/sub] = 2^(2^m) + 1, where q is [i]an odd prime[/i]. In every case I checked, it was true that Mod(q,p)^2^n = Mod(1,p) [that is, that q is a q-th power residue (mod p)]. I suspect this might always be true when q is [i]an odd prime[/i] (my hypothesis), but don't see an obvious proof.

Before trying to prove it myself (assuming it's not already known), I tried checking to make sure there weren't any obvious counterexamples.

If somebody knows (of) a proof, please point me in the right direction.

Meanwhile...

I have counterexamples for [i]composite[/i] odd q, where the prime p = q*2^n + 1 divides 2^(2^m) + 1, but Mod(q,p)^(2^n) is not Mod(1,p).

I also have counterexamples for p = 5*2^n + 1 which do [i]not[/i] divide Fermat numbers; the smallest is p = 11: Mod(5, 11)^2 = Mod(3,11), not Mod(1,11).

The following list, culled from a web page, is of triples [m, q, n] where p = q*2^n + 1 divides 2^(2^m) + 1, and q is [i]prime[/i].

[code]v=[[5, 5, 7], [12, 7, 14], [12, 397, 16], [12, 17353230210429594579133099699123162989482444520899, 15], [18, 13, 20], [19, 33629, 21], [19, 8962167624028624126082526703, 22], [23, 5, 25], [25, 48413, 29], [36, 5, 39], [38, 3, 41], [55, 29, 57], [71, 683, 73], [73, 5, 75], [81, 271, 84], [117, 7, 120], [125, 5, 127], [144, 17, 147], [172, 20569603303, 174], [207, 3, 209], [228, 29, 231], [251, 85801657, 254], [284, 7, 290], [316, 7, 320], [416, 38039, 419], [547, 77377, 550], [556, 127, 558], [579, 63856313, 581], [637, 11969, 643], [642, 52943971, 644], [744, 17, 747], [1945, 5, 1947], [2023, 29, 2027], [2089, 431, 2099], [3056, 3370842847, 3058], [3310, 5, 3313], [3723, 13308899, 3725], [4724, 29, 4727], [5320, 21341, 5323], [6537, 17, 6539], [6835, 19, 6838], [9448, 19, 9450], [14276, 157, 14280], [18749, 11, 18759], [23288, 19, 23290], [23471, 5, 23473], [30256, 121531, 30260], [48624, 28949, 48627], [79221, 6089, 79223], [95328, 7, 95330], [114293, 13, 114296], [125410, 5, 125413], [138557, 7333, 138560], [157167, 3, 157169], [213319, 3, 213321], [287384, 211, 287388], [303088, 3, 303093], [382447, 3, 382449], [472097, 89, 472099], [585042, 151, 585044], [617813, 659, 617815], [960897, 11, 960901], [1494096, 131, 1494099], [2145351, 3, 2145353], [2167797, 7, 2167800], [2478782, 3, 2478785], [3329780, 193, 3329782]][/code]

I only checked up to [95328, 7, 95330]. The checking... ... was... ... ... ... ... ... ... ... ... getting... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... slow.

I would appreciate it if someone could check whether (Mod(q,p)^(2^n) = Mod(1,p) for the ones with larger m.

 All times are UTC. The time now is 04:05.