cp's OEIS Frontend

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

%I A281069 #44 Sep 10 2024 00:25:13
%S A281069 2,10,30,3458,29526,5437705,91604415,1190857395,26535163830,
%T A281069 344957129790
%N A281069 Least k such that phi(k) is an n-th power when k is the product of n distinct primes.
%C A281069 Subsequence of A166955.
%C A281069 Corresponding values of phi(k) are 1, 4, 8, 1296, 7776, 2985984, ...
%C A281069 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.
%C A281069 a(11) <= 5703406198237930, a(12) <= 178435136773443810, a(13) <= 4961806417984478790. - _Daniel Suteu_, Apr 04 2021
%H A281069 W. D. Banks and F. Luca, <a href="https://faculty.missouri.edu/~bankswd/papers/2011_power_totients_almost_primes_published_version.pdf">Power totients with almost primes</a>, author's copy, Integers 11A (2011), 307-313.
%H A281069 Tristan Freiberg, <a href="http://arxiv.org/abs/1008.1978">Products of shifted primes simultaneously taking perfect power values</a>, arXiv:1008.1978 [math.NT], 2010.
%H A281069 Tristan Freiberg and Carl Pomerance, <a href="https://doi.org/10.1142/S179304211550102X">A note on square totients</a>, International Journal of Number Theory, Volume 11, Issue 08, December 2015.
%e A281069 a(4) = 3458 = 2 * 7 * 13 * 19 and phi(3458) = (2-1)*(7-1)*(13-1)*(19-1) = 6^4.
%o A281069 (PARI) a(n) = {my(k=2); while (!(issquarefree(k) && (omega(k)==n) && (ispower(eulerphi(k),n))), k++); k;} \\ _Michel Marcus_, Jan 16 2017
%o A281069 (Python)
%o A281069 from itertools import count
%o A281069 from math import isqrt, prod
%o A281069 from sympy import perfect_power, primefactors, primerange, integer_nthroot, primepi
%o A281069 def A281069(n):
%o A281069     def squarefreealmostprimepi(n,k):
%o A281069         if k==0: return int(n>=1)
%o A281069         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)))
%o A281069         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))
%o A281069     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
%Y A281069 Cf. A000010, A001597, A005117, A166955, A281140.
%K A281069 nonn,more
%O A281069 1,1
%A A281069 _Altug Alkan_, Jan 14 2017
%E A281069 a(9)-a(10) from _Jinyuan Wang_, Nov 08 2020