mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2019-10-17, 01:17   #1
miket
 
May 2013

32 Posts
Default 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,

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)
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)?

Last fiddled with by miket on 2019-10-17 at 01:35 Reason: add question
miket is offline   Reply With Quote
Old 2019-10-17, 15:03   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

512510 Posts
Default

Quote:
Originally Posted by miket View Post
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>
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 different powers of 2.

Third, if n is prime, 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 is offline   Reply With Quote
Old 2019-10-17, 19:41   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

120058 Posts
Default

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 F23471

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 F23, I haven't checked them.
Dr Sardonicus is offline   Reply With Quote
Old 2019-10-18, 06:09   #4
miket
 
May 2013

10012 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
First, I don't understand why n = 3 isn't on the list.

Thanks for your check.
'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'.
miket is offline   Reply With Quote
Old 2019-10-19, 12:16   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

53·41 Posts
Default

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 is offline   Reply With Quote
Old 2019-10-21, 20:20   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

512510 Posts
Default

This topic inspired me to formulate a hypothesis.

I checked some of the primes p = q*2^n + 1 which divide Fm = 2^(2^m) + 1, where q is an odd prime. 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 an odd prime (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 composite 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 not 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 prime.

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

Last fiddled with by Dr Sardonicus on 2019-10-21 at 21:07 Reason: infxig sytpo
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A new sequence devarajkandadai Miscellaneous Math 3 2020-12-01 22:08
Primes in n-fibonacci sequence and n-step fibonacci sequence sweety439 And now for something completely different 17 2017-06-13 03:49
What's the next in the sequence? roger Puzzles 16 2006-10-18 19:52
Mersenne prime related shirts and other items adpowers Lounge 40 2004-08-12 22:05
Number of "items" per page... Xyzzy Lounge 18 2002-10-30 21:54

All times are UTC. The time now is 01:13.


Wed Dec 1 01:13:16 UTC 2021 up 130 days, 19:42, 0 users, load averages: 1.42, 1.45, 1.42

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.