View Single Post
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