login
A291972
a(n) is the smallest k such that psi(k)/phi(k) is prime where k is the product of n distinct primes.
1
2, 15, 78, 910, 16770, 399126, 4849845, 27606810, 1543735830, 46091541210, 3546424866270, 84404911817226, 10124919639292458, 388334647332742110, 50538403948689240870, 209239673740280773590, 27738324896530958239530, 3327392973457778860124490
OFFSET
1,1
COMMENTS
Least k = Product_{i=1..n} p_i such that Product_{i=1..n} (p_i+1)/(p_i-1) is a prime number where p_i is i-th prime divisor of k.
All terms are squarefree. - Charles R Greathouse IV, Sep 07 2017
EXAMPLE
a(3) = 78 = 2*3*13 because psi(78) / phi(78) = 7 is prime and 78 is the least number with this property.
PROG
(PARI) has(f, n)=if(#f~ != n || vecmax(f[, 2])>1, return(0)); my(p=prod(i=1, #f~, 2/(f[i, 1]-1) + 1)); denominator(p)==1 && isprime(p)
a(n)=my(mn=prod(i=1, n, prime(i)), mx=2*mn); while(1, forfactored(k=mn, mx, if(has(k[2], n), return(k[1]))); mn=mx; mx*=2) \\ Charles R Greathouse IV, Sep 07 2017
(Python)
from itertools import count
from fractions import Fraction
from math import prod, isqrt
from sympy import primefactors, isprime, primerange, integer_nthroot, primepi
def A291972(n):
def squarefreealmostprimepi(n, k):
if k==0: return int(n>=1)
def g(x, a, b, c, m): yield from (((d, ) for d in enumerate(primerange(b+1, isqrt(x//c)+1), a+1)) if m==2 else (((a2, b2), )+d for a2, b2 in enumerate(primerange(b+1, integer_nthroot(x//c, m)[0]+1), a+1) for d in g(x, a2, b2, c*b2, m-1)))
return int(sum(primepi(n//prod(c[1] for c in a))-a[-1][0] for a in g(n, 0, 1, 1, k)) if k>1 else primepi(n))
return next(k for k in (squarefreealmostprime(i, n) for i in count(1)) if (m:=prod(Fraction(p+1, p-1) for p in primefactors(k))).denominator==1 and isprime(m.numerator)) # Chai Wah Wu, Sep 09 2024
CROSSREFS
Sequence in context: A102289 A041243 A216247 * A056079 A266622 A036239
KEYWORD
nonn
AUTHOR
Altug Alkan, Sep 07 2017
EXTENSIONS
a(10)-a(18) from Charles R Greathouse IV, Sep 07 2017
STATUS
approved