A281069 Least k such that phi(k) is an n-th power when k is the product of n distinct primes.

2, 10, 30, 3458, 29526, 5437705, 91604415, 1190857395, 26535163830, 344957129790

Offset: 1

Author

Altug Alkan, Jan 14 2017

Keywords

• nonn
• more

Comments

Subsequence of A166955.

Corresponding values of phi(k) are 1, 4, 8, 1296, 7776, 2985984, ...

Freiberg (Theorem 1.2) shows that there are >> (n*x^(1/n))/(log x)^(n+2) such values of k up to x. He calls the set of such numbers B*(x;-1;n). In particular, a(n) exists for each n.

a(11) <= 5703406198237930, a(12) <= 178435136773443810, a(13) <= 4961806417984478790. - Daniel Suteu, Apr 04 2021

Examples

			a(4) = 3458 = 2 * 7 * 13 * 19 and phi(3458) = (2-1)*(7-1)*(13-1)*(19-1) = 6^4.
		

Links

• W. D. Banks and F. Luca, Power totients with almost primes, author's copy, Integers 11A (2011), 307-313.
• Tristan Freiberg, Products of shifted primes simultaneously taking perfect power values, arXiv:1008.1978 [math.NT], 2010.
• Tristan Freiberg and Carl Pomerance, A note on square totients, International Journal of Number Theory, Volume 11, Issue 08, December 2015.

Crossrefs

Cf. A000010, A001597, A005117, A166955, A281140.

Programs

PARI

a(n) = {my(k=2); while (!(issquarefree(k) && (omega(k)==n) && (ispower(eulerphi(k),n))), k++); k;} \\ Michel Marcus, Jan 16 2017

Python

from itertools import count
from math import isqrt, prod
from sympy import perfect_power, primefactors, primerange, integer_nthroot, primepi
def A281069(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 (p:=perfect_power(prod(p-1 for p in primefactors(k)))) and p[1] == n) if n>1 else 2 # Chai Wah Wu, Sep 09 2024

Extensions

a(9)-a(10) from Jinyuan Wang, Nov 08 2020