

A260119


a(n) is the least positive integer k such that 2^n1 and k^n1 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Note that (2^n1)^n1 is always relatively prime to 2^n1.
a(72) > 10^8.
According to the conjecture given in A086892, a(n) = 3 infinitely often.
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)
Both conjectures are true.
Since (2k)^n  1 = (k^n)*(2^n  1) + (k^n  1), GCD((2k)^n  1, 2^n1) = GCD(k^n1, 2^n1). Thus a(n) is always odd.
If p is an odd prime such that p1 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



EXAMPLE

Since 2^51 = 31 and 3^51 = 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:


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^n1, k^n1)
return k
print([min_k(n) for n in [1..71]])
(PARI) a(n) = {my(k=1, pt = 2^n1); while (gcd(pt, k^n1) != 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)^n1, 2^n1)==1, return(p*i))); for(i=1, n, if(gcd(p^n1, 2^n1) == 1, return(p), p=nextprime(p+1))); forstep(i=1, 100000, 2, if(gcd((i)^n1, 2^n1)==1, return(i)))} \\ David A. Corneth, Sep 01 2015


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



