login
A260119
a(n) is the least positive integer k such that 2^n-1 and k^n-1 are relatively prime.
4
1, 3, 3, 15, 3, 21, 3, 45, 3, 99, 5, 1365, 3, 3, 3, 765, 3, 399, 3, 1815, 3, 69, 5, 1365, 3, 3, 3, 435, 3, 35805, 3, 765, 5, 3, 7, 2878785, 3, 3, 3, 20295, 3, 903, 5, 1035, 3, 141, 3, 116025, 3, 99, 3, 795, 3, 399, 5, 435, 3, 177, 3, 85180095, 3, 3, 3, 765, 3, 32361, 3, 45, 5, 11715, 3
OFFSET
1,2
COMMENTS
Note that (2^n-1)^n-1 is always relatively prime to 2^n-1.
a(72) > 10^8.
According to the conjecture given in A086892, a(n) = 3 infinitely often.
From David A. Corneth, Aug 17 2015: (Start)
Conjecture 1: a(n) is never divisible by 2.
Conjecture 2: a(n) is of the form q * m where q is the product of all odd primes that are one more than a divisor of n.
(End)
From Robert Israel, Sep 02 2015: (Start)
Both conjectures are true.
Since (2k)^n - 1 = (k^n)*(2^n - 1) + (k^n - 1), GCD((2k)^n - 1, 2^n-1) = GCD(k^n-1, 2^n-1). Thus a(n) is always odd.
If p is an odd prime such that p-1 divides n, then k^n - 1 is divisible by p for all k coprime to p (and in particular k=2). Thus a(n) must be divisible by p, and thus by the product of all such p.
(End)
LINKS
Robert Israel, Table of n, a(n) for n = 1..10000 [Terms 72 through 5000 were computed by David A. Corneth, Aug 17 2015]
EXAMPLE
Since 2^5-1 = 31 and 3^5-1 = 242 are relatively prime, a(5) = 3.
The divisors of 72 are 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72;
Adding one to each divisor gives 3, 4, 5, 7, 9, 10, 13, 19, 25, 37, 73;
The odd primes in this list are 3, 5, 7, 13, 19, 37, 73;
The product of these primes is 3 * 5 * 7 * 13 * 19 * 37 * 73 = 70050435;
Thus a(72) is of the form 70050435 * m.
MAPLE
f:= proc(n) local P, Q, M, k, kn;
P:= select(isprime, map(t -> t+1, numtheory:-divisors(n)) minus {2});
M:= convert(P, `*`);
Q:= 2^n - 1;
for k from M by 2*M do
kn:= k &^ n - 1 mod Q;
if igcd(kn, Q) = 1 then
return k
fi
od
end proc:
map(f, [$1..100]); # Robert Israel, Sep 02 2015
MATHEMATICA
Table[k = 1; While[! CoprimeQ[2^n - 1, k^n - 1], k++]; k, {n, 59}] (* Michael De Vlieger, Sep 01 2015 *)
PROG
(Sage)
def min_k(n):
g, k=2, 0
while g!=1:
k=k+1
g=gcd(2^n-1, k^n-1)
return k
print([min_k(n) for n in [1..71]])
(PARI) a(n) = {my(k=1, pt = 2^n-1); while (gcd(pt, k^n-1) != 1, k++); k; } \\ Michel Marcus, Jul 17 2015 && Jan 27 2016
(PARI) conjecture_a(n) = {my(d=divisors(n)); v=select(x->isprime(x+1), select(y->y%2==0, d)); v+= vector(#v, i, 1); p=prod(i=1, #v, v[i]); if(p==1&&n!=1, p=3);
forstep(i=1, p, 2, if(gcd((p * i)^n-1, 2^n-1)==1, return(p*i))); for(i=1, n, if(gcd(p^n-1, 2^n-1) == 1, return(p), p=nextprime(p+1))); forstep(i=1, 100000, 2, if(gcd((i)^n-1, 2^n-1)==1, return(i)))} \\ David A. Corneth, Sep 01 2015
CROSSREFS
Cf. A086892.
Sequence in context: A282388 A131943 A226139 * A368117 A282009 A282485
KEYWORD
nonn
AUTHOR
Tom Edgar, Jul 17 2015
STATUS
approved