A068211 -id:A068211 - cp's OEIS frontend

A070003 Numbers divisible by the square of their largest prime factor.

4, 8, 9, 16, 18, 25, 27, 32, 36, 49, 50, 54, 64, 72, 75, 81, 98, 100, 108, 121, 125, 128, 144, 147, 150, 162, 169, 196, 200, 216, 225, 242, 243, 245, 250, 256, 288, 289, 294, 300, 324, 338, 343, 361, 363, 375, 392, 400, 432, 441, 450, 484, 486, 490, 500, 507

Offset: 1

Labos Elemer, May 07 2002

nonn

Numbers n such that P(phi(n)) - phi(P(n)) = 1, where P(x) is the largest prime factor of x. P(phi(n)) - phi(P(n)) = A006530(A000010(n)) - A000010(A006530(n)).
Numbers n such that the value of the commutator of phi and P functions at n is -1.
Equivalently, n such that n and phi(n) have the same largest prime factor since Phi(p) = p-1 if p is prime. - Benoit Cloitre, Jun 08 2002
Since n is divisible by P(n)^2, n cannot divide P(n)! and so A057109 is a supersequence. Hence all A002034(a(n)) are composite. - Jonathan Sondow, Dec 28 2004
A225546 defines a self-inverse bijection between this sequence and A335740, considered as sets. - Peter Munn, Jul 19 2020

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Paul Erdős and Ron L. Graham, On products of factorials, Bull. Inst. Math. Acad. Sinica 4:2 (1976), pp. 337-355. [alternate link]
Paul Erdős and Ilias Kastanas, Solution 6674:The smallest factorial that is a multiple of n, Amer. Math. Monthly 101 (1994) 179.
A. J. Kempner, Miscellanea, Amer. Math. Monthly, 25 (1918), 201-210. See Section II, "Concerning the smallest integer m! divisible by a given integer n."
Eric Weisstein's World of Mathematics, Greatest Prime Factor
Eric Weisstein's World of Mathematics, Totient Function

Subsequence of A057109, A122145.
Complement within A020725 of A102750.
Cf. A000010, A006530, A068211, A070777, A070812, A070002, A070004, A007283, A070813, A070814, A070815, A070816, A002034, A102067, A102068.
Related to A335740 via A225546.
A195212 is a subsequence.
Cf. A319988 (characteristic function). Positions of odd terms > 1 in A122111.

isA070003 := proc(n)
    if modp(n,A006530(n)^2) = 0 then # code re-use
        true;
    else
        false;
    end if;
end proc:
A070003 := proc(n)
    option remember ;
    if n =1 then
        4;
    else
        for a from procname(n-1)+1 do
            if isA070003(a) then
                return a
            end if;
        end do:
    end if;
end proc:
seq( A070003(n),n=1..80) ; # R. J. Mathar, Jun 27 2024

p[n_] := FactorInteger[n][[-1, 1]]; ep[n_] := EulerPhi[n]; fQ[n_] := p[ep[n]] == 1 + ep[p[n]]; Select[ Range[ 510], fQ] (* Robert G. Wilson v, Mar 26 2012 *)
Select[Range[500], FactorInteger[#][[-1,2]] > 1 &] (* T. D. Noe, Dec 06 2012 *)

for(n=3,1000,if(component(component(factor(n),1),omega(n))==component(component(factor(eulerphi(n)),1),omega(eulerphi(n))),print1(n,",")))

is(n)=my(f=factor(n)[,2]);f[#f]>1 \\ Charles R Greathouse IV, Mar 21 2012

sm(lim,mx)=if(mx==2,return(vector(log(lim+.5)\log(2)+1,i,1<<(i-1))));my(v=[1]);forprime(p=2,min(mx,lim),v=concat(v,p*sm(lim\p,p)));vecsort(v)
list(lim)=my(v=[]);forprime(p=2,sqrt(lim),v=concat(v,p^2*sm(lim\p^2,p)));vecsort(v) \\ Charles R Greathouse IV, Mar 27 2012

from sympy import factorint
def ok(n): f = factorint(n); return f[max(f)] >= 2
print(list(filter(ok, range(4, 508)))) # Michael S. Branicky, Apr 08 2021

Erdős proved that there are x * exp(-(1 + o(1))sqrt(log x log log x)) members of this sequence up to x. - Charles R Greathouse IV, Mar 26 2012

New name from Jonathan Sondow and Charles R Greathouse IV, Mar 27 2012

A035095 Smallest prime congruent to 1 (mod prime(n)).

Original entry on oeis.org

3, 7, 11, 29, 23, 53, 103, 191, 47, 59, 311, 149, 83, 173, 283, 107, 709, 367, 269, 569, 293, 317, 167, 179, 389, 607, 619, 643, 1091, 227, 509, 263, 823, 557, 1193, 907, 1571, 653, 2339, 347, 359, 1087, 383, 773, 3547, 797, 2111, 2677, 5449, 2749, 467

Offset: 1

Labos Elemer

nonn

This is a version of the "least prime in special arithmetic progressions" problem.
Smallest numbers m such that largest prime factor of Phi(m) = prime(n), the n-th prime, also seems to be prime and identical to n-th term of A035095. See A068211, A068212, A065966: Min[x : A068211(x)=prime(n)] = A035095(n); e.g., Phi(a(7)) = Phi(103) = 2*3*17, of which 17 = p(7) is the largest prime factor, arising first here.
It appears that A035095, A066674, A125878 are probably all the same, but see the comments in A066674. - N. J. A. Sloane, Jan 05 2013
Minimum of the smallest prime factors of F(n,i) = (i^prime(n)-1)/(i-1), when i runs through all integers in [2, prime(n)]. Every prime factor of F(n,i) is congruent to 1 modulo prime(n). - Vladimir Shevelev, Nov 26 2014
Conjecture: a(n) is the smallest prime p such that gpf(p-1) = prime(n). See A023503. - Thomas Ordowski, Aug 06 2017
For n>1, a(n) is the smallest prime congruent to 1 mod (2*prime(n)). - Chai Wah Wu, Apr 28 2025

			a(8) = 191 because in the prime(8)k+1 = 19k+1 sequence, 191 is the smallest prime.

E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Bd 1 (reprinted Chelsea 1953).
E. C. Titchmarsh, A divisor problem, Renc. Circ. Math. Palermo, 54 (1930) pp. 414-429.
P. Turan, Über Primzahlen der arithmetischen Progression, Acta Sci. Math. (Szeged), 8 (1936/37) pp. 226-235.

T. D. Noe, Table of n, a(n) for n = 1..10000
P. Erdős, On some application of Brun's method, Acta Sci. Math (Szeged), v. 13, 1949, pp. 57-63.
A. Granville and C. Pomerance, On the least prime in certain arithmetic progressions
A. Granville and C. Pomerance, On the least prime in certain arithmetic progressions J. Lond Math Soc s2-41 (2) (1990), pp. 193-200.
D. R. Heath-Brown, almost-primes in arithmetic progressions in short intervals, Math Proc Cambr. Phil Soc v 83 (1978), pp. 357-375.
D. R. Heath-Brown, Siegel zeros and the least prime in arithmetic progression, Quart. J. of Math 41 (49) (1990), pp. 405-418.
H.-J. Kanold, Uber Primzahlen in arithmetischen Folgen, Math. Ann. v 156 (1964) pp. 393-395.
U. V. Linnik, On the least prime in an arithmetic progression. I. The basic theorem, Rec. Math (N.S.) v 15 (57) (1944), pp 139-178. MR0012111
C. Pomerance, A note on the least prime in an arithmetic progression J. Number Theory 12 (2) (1980), pp. 218-223.
K. Prachar, Uber die kleinste Primzahl in einer arithmetischen Reihe, J Reine Angew Math. 206 (1961) pp. 3-4.
A. Schinzel, Remark on the paper of K. Prachar Uber die kleinste.., J. Reine Angew Math. v 210 (1962) pp. 122-122.
S. S. Wagstaff, Jr., The irregular primes to 125000, Math. Comp., 32 (1978) pp. 583-591.
S. S. Wagstaff, Jr, Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus, Math. Comp., 33 (147) (1979) pp. 1073-1080.
Index entries for sequences related to primes in arithmetic progressions

Cf. A034694, A032448, A006530, A006093, A035096, A000040, A019434, A058383.
Cf. A068211, A068212, A065966, A000010, A070844-A070858, A061092.
Cf. A000040.

a[n_] := Block[{p = Prime[n]}, r = 1 + p; While[ !PrimeQ[r], r += p]; r]; Array[a, 51] (* Jean-François Alcover, Sep 20 2011, after PARI *)
a[n_]:=If[n<2,3,Block[{p=Prime[n]},r=1+2*p;While[!PrimeQ[r],r+=2*p]];r];Array[a,51] (* Zak Seidov, Dec 14 2013 *)

a(n)=local(p,r);p=prime(n);r=1;while(!isprime(r),r+=p);r

{my(N=66); forprime(p=2, , forprime(q=p+1,10^10, if((q-1)%p==0, print1(q,", "); N-=1; break)); if(N==0,break)); } \\ Joerg Arndt, May 27 2016

from itertools import count
from sympy import prime, isprime
def A035095(n): return 3 if n==1 else next(filter(isprime,count((p:=prime(n)<<1)+1,p))) # Chai Wah Wu, Apr 28 2025

According to a long-standing conjecture (see the 1979 Wagstaff reference), a(n) <= prime(n)^2 + 1. This would be sufficient to imply that a(n) is the smallest prime such that greatest prime divisor of a(n)-1 is prime(n), the n-th prime: A006530(a(n)-1) = A000040(n). This in turn would be sufficient to imply that no value occurs twice in this sequence. - Franklin T. Adams-Watters, Jun 18 2010

a(n) = 1 + A035096(n)*A000040(n). - Zak Seidov, Dec 27 2013

Edited by Franklin T. Adams-Watters, Jun 18 2010
Minor edits by N. J. A. Sloane, Jun 27 2010
Edited by N. J. A. Sloane, Jan 05 2013

A070812 a(n) = phi(gpf(n)) - gpf(phi(n)) = A000010(A006530(n)) - A006530(A000010(n)).

Original entry on oeis.org

0, -1, 2, 0, 3, -1, -1, 2, 5, 0, 9, 3, 2, -1, 14, -1, 15, 2, 3, 5, 11, 0, -1, 9, -1, 3, 21, 2, 25, -1, 5, 14, 3, -1, 33, 15, 9, 2, 35, 3, 35, 5, 1, 11, 23, 0, -1, -1, 14, 9, 39, -1, 5, 3, 15, 21, 29, 2, 55, 25, 3, -1, 9, 5, 55, 14, 11, 3, 63, -1, 69, 33, -1, 15, 5, 9, 65, 2, -1, 35, 41, 3, 14, 35, 21, 5, 77, 1, 9, 11, 25, 23, 15, 0, 93, -1, 5

Offset: 3

Labos Elemer, May 09 2002

sign

Value of commutator[A000010, A006530] at n.

			Cases of n when a(n) = 1, -1, 2 or 0 are listed in A070002, A070003, A070004, A007283 respectively. Further regular solutions: if a(n)=3, then n=7k, where k has prime divisors < 7; if a(n)=5, then n=11k, where k has no prime divisors >=11; if a(n)=25, then mostly (not always!) n=31k ...

Michael De Vlieger, Table of n, a(n) for n = 3..10000
Michael De Vlieger, Log log scatterplot of a(n)+2, n = 3..10^5.

Cf. A000010, A006530, A070777, A068211, A070002, A070003, A070004, A007283.

pf[x_] := Part[Reverse[Flatten[FactorInteger[x]]], 2] Table[EulerPhi[pf[u]]-pf[EulerPhi[u]], {u, 3, 128}]

gpf(n)=my(f=factor(n)[,1]);f[#f]
a(n)=gpf(n)-gpf(eulerphi(n))-1 \\ Charles R Greathouse IV, Feb 19 2013

a(n) = A070777(n) - A068211(n).

A070777 a(1) = 1; a(n) = (largest prime factor of n) - 1.

Original entry on oeis.org

1, 1, 2, 1, 4, 2, 6, 1, 2, 4, 10, 2, 12, 6, 4, 1, 16, 2, 18, 4, 6, 10, 22, 2, 4, 12, 2, 6, 28, 4, 30, 1, 10, 16, 6, 2, 36, 18, 12, 4, 40, 6, 42, 10, 4, 22, 46, 2, 6, 4, 16, 12, 52, 2, 10, 6, 18, 28, 58, 4, 60, 30, 6, 1, 12, 10, 66, 16, 22, 6, 70, 2, 72, 36, 4, 18, 10, 12, 78, 4, 2, 40, 82, 6

Offset: 1

Labos Elemer, May 07 2002

Also a(n) = Euler Phi of largest prime factor of n (previous name).

a(m*n) = max(a(m), a(n)). - Robert Israel, May 19 2015

			102 = 2*3*17, so a(102) = 17 - 1 = 16.

Cf. A000010, A006530, A068211, A070812.

with(numtheory): A070777 := n -> `if`(n=1,1,phi(max(op(factorset(n))))): # Peter Luschny, Oct 23 2010

a[n_] := EulerPhi[Last[FactorInteger[n]][[1]]]; Table[a[n], {n, 1, 200}] (* José María Grau Ribas, Feb 21 2010 *)

a(n) = if (n==1, 1, vecmax(factor(n)[,1]) - 1); \\ after A006530; Michel Marcus, May 19 2015

a(n) = A000010(A006530(n)) = A006530(n) - 1 if n >= 2.

New name from Michel Marcus, May 19 2015

A065966 Numbers k such that phi(k) / 2 is prime.

Original entry on oeis.org

5, 7, 8, 9, 10, 11, 12, 14, 18, 22, 23, 46, 47, 59, 83, 94, 107, 118, 166, 167, 179, 214, 227, 263, 334, 347, 358, 359, 383, 454, 467, 479, 503, 526, 563, 587, 694, 718, 719, 766, 839, 863, 887, 934, 958, 983, 1006, 1019, 1126, 1174, 1187, 1283, 1307, 1319

Offset: 1

Joseph L. Pe, Dec 08 2001

nonn

This is probably an infinite sequence, but a proof would be nice. Are there infinitely many consecutive terms of the sequence which are also consecutive integers? (For example, 7, 8 and 46, 47.)

Apart from 8, 9, 12 and 18, all the terms of the sequence are safe primes or twice safe primes. It is not known if there are infinitely many safe primes (cf. A005385, A005384). For consecutive terms of the sequence which are also consecutive integers see A066179. - Vladeta Jovovic, Dec 16 2001

			phi(46)/2 = 22/2 = 11, a prime.

Harry J. Smith, Table of n, a(n) for n = 1..1000
André Hernández-Espiet, Reyes M. Ortiz-Albino, On the Characterization of tau(n)-Atoms, arXiv:1905.02834 [math.NT], 2019. See Proposition 3.1.

Cf. A000010, A005385, A005384, A066179, A006530, A052126, A068211, A068212.

Select[Range[1400],PrimeQ[EulerPhi[#]/2]&] (* Harvey P. Dale, Feb 11 2020 *)

for(n=3,5000, if(isprime(eulerphi(n)/2),print1(n,",")))

{ n=0; for (m=3, 10^9, if (isprime(eulerphi(m)/2), write("b065966.txt", n++, " ", m); if (n==1000, return)) ) } \\ Harry J. Smith, Nov 05 2009

Numbers k such that A068212(k) = 2.

More terms from Jason Earls, Dec 09 2001

Edited by Charles R Greathouse IV, Mar 18 2010

A070004 Numbers of the form 52^n or 532^n; a(n) = 5A029744(n).

Original entry on oeis.org

5, 10, 15, 20, 30, 40, 60, 80, 120, 160, 240, 320, 480, 640, 960, 1280, 1920, 2560, 3840, 5120, 7680, 10240, 15360, 20480, 30720, 40960, 61440, 81920, 122880, 163840, 245760, 327680, 491520, 655360, 983040, 1310720, 1966080, 2621440

Offset: 1

Labos Elemer, May 07 2002

Old name was: Numbers n such that phi(P(n)) - P(phi(n)) = 2, where P(x)=largest prime factor of x, or A000010(A006530(n))-A006530(A000010(n))=2.

Solutions to phi(P(x))-P(phi(x))=c, presence or absence of special prime factors in x are usually derivable.

Index entries for linear recurrences with constant coefficients, signature (0,2).

Cf. A000010, A006530, A068211, A070777, A070812, A070002, A070003, A007283, A070813-A070816.

pf[x_] := Part[Reverse[Flatten[FactorInteger[x]]], 2]; Do[s=EulerPhi[pf[n]]-pf[EulerPhi[n]]; If[Equal[s, 2], Print[n]], {n, 3, 1000000}]
Union[Flatten[Table[2^n {5,15},{n,0,20}]]] (* or *) Join[ {5}, LinearRecurrence[ {0,2},{10,15},40]] (* Harvey P. Dale, Dec 23 2014 *)

gpf(n)=if(n>1,my(f=factor(n)[,1]);f[#f],1)
is(n)=eulerphi(gpf(n))-gpf(eulerphi(n))==2 \\ Charles R Greathouse IV, Feb 19 2013

a(n) = 5*A029744(n); numbers of the forms 5*2^n and 15*2^n.
G.f.: 5*x*(x+1)^2/(1-2*x^2). - Ralf Stephan, Jul 15 2013
Sum_{n>=1} 1/a(n) = 8/15. - Amiram Eldar, Jan 02 2021

Simpler name by Joerg Arndt, Jul 16 2013

A070002 Numbers k such that phi(P(k)) - P(phi(k)) = 1, where P(k) is the largest prime factor of k.

Original entry on oeis.org

45, 90, 135, 175, 180, 270, 350, 360, 405, 525, 540, 700, 720, 810, 875, 1050, 1080, 1215, 1400, 1440, 1573, 1575, 1620, 1750, 2100, 2160, 2430, 2625, 2800, 2880, 3146, 3150, 3240, 3500, 3645, 4200, 4320, 4375, 4719, 4725, 4860, 5250, 5491, 5600, 5760

Offset: 1

Labos Elemer, May 07 2002

nonn

phi(P(k)) - P(phi(k)) = A000010(A006530(k)) - A006530(A000010(k)) = 1, where P(k) = largest prime factor of k. Value of commutator of phi and P functions at k equals 1.

Many but not all terms are divisible by 5.

			m = 77077 = 7*7*11*11*13*13 is here because P(m) = 13, phi(P(13)) = 12, phi(m) = 55440 = 2*2*2*2*3*3*5*7*11 with P(Phi(55440)) = 13 and the difference is 13 - 12 = 1.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A006530, A068211, A070777, A070812, A070003, A070004, A007283, A070813, A070814, A070815, A070816.

pf[n_] := FactorInteger[n][[-1, 1]];
Do[s=EulerPhi[pf[n]]-pf[EulerPhi[n]]; If[Equal[s, 1], Print[n]], {n, 3, 100000}]

A068212 a(n) = phi(n) divided by its largest prime factor.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 2, 2, 2, 2, 4, 2, 4, 4, 8, 2, 6, 4, 4, 2, 2, 4, 4, 4, 6, 4, 4, 4, 6, 8, 4, 8, 8, 4, 12, 6, 8, 8, 8, 4, 6, 4, 8, 2, 2, 8, 6, 4, 16, 8, 4, 6, 8, 8, 12, 4, 2, 8, 12, 6, 12, 16, 16, 4, 6, 16, 4, 8, 10, 8, 24, 12, 8, 12, 12, 8, 6, 16, 18, 8, 2, 8, 32, 6, 8, 8, 8, 8, 24, 4, 12, 2, 24

Offset: 3

Labos Elemer, Feb 21 2002

nonn

Cf. A000010, A006530, A052126, A068211.

epn[n_]:=Module[{e=EulerPhi[n]},e/FactorInteger[e][[-1,1]]]; Array[ epn,100,3] (* Harvey P. Dale, Apr 18 2012 *)

a(n) = A052126(A000010(n)) = A000010(n)/A068211(n) = A000010(n)/A006530(A000010(n)).

A071964 Numbers k such that k = Gpf(k) * Gpf(phi(k)) where Gpf(k) = A006530(k) is the greatest prime factor of k.

Original entry on oeis.org

4, 6, 9, 10, 21, 25, 34, 39, 49, 55, 57, 111, 121, 155, 169, 203, 205, 219, 253, 289, 291, 301, 305, 327, 361, 489, 497, 505, 514, 529, 579, 689, 737, 755, 791, 841, 889, 905, 961, 979, 1027, 1081, 1205, 1255, 1299, 1355, 1369, 1379, 1461, 1477, 1681, 1703

Offset: 1

Benoit Cloitre, Jun 16 2002

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010 (phi), A006530, A068211.

Select[Range[1800],FactorInteger[#][[-1,1]]FactorInteger[EulerPhi[#]][[-1,1]] == #&] (* Harvey P. Dale, Mar 25 2023 *)

for(n=1,3000,if(vecmax(component(factor(n),1))*vecmax(component(factor(eulerphi(n)),1))==n,print1(n,",")))

is(k) = if(k > 2, my(f = factor(k)); k == f[#f~, 1] * vecmax(factor(eulerphi(f))[, 1]), 0); \\ Amiram Eldar, Oct 28 2024

A070817 a(n) = floor(n/2) - gpf(phi(n)), where gpf(n) is the largest prime factor of n.

Original entry on oeis.org

-1, 0, 0, 1, 0, 2, 1, 3, 0, 4, 3, 4, 5, 6, 6, 6, 6, 8, 7, 6, 0, 10, 7, 10, 10, 11, 7, 13, 10, 14, 11, 15, 14, 15, 15, 16, 16, 18, 15, 18, 14, 17, 19, 12, 0, 22, 17, 20, 23, 23, 13, 24, 22, 25, 25, 22, 0, 28, 25, 26, 28, 30, 29, 28, 22, 32, 23, 32, 28, 33, 33, 34, 32, 35, 33, 36, 26, 38, 37, 36, 0, 39, 40, 36, 36, 39, 33, 42, 42, 35, 41, 24

Offset: 3

Labos Elemer, May 10 2002

			For n=3, floor(3/2) = 1, phi(3) = 2, gpf(2) = 2, a(3) = 1 - 2 = -1.
For n=107, floor(107/2) = 53, phi(107) = 2*53, gpf(106) = 53, a(107) = 53 - 53 = 0.
For n=128, floor(128/2) = 64, gpf(phi(128)) = gpf(64) = 2, a(128) = 64 - 2 = 62.

Cf. A000010, A004526, A005384, A005385, A006530, A068211.

mf[x_] := Part[Reverse[Flatten[FactorInteger[x]]], 2] Table[Floor[n/2//N]-mf[EulerPhi[n]], {w, 3, 128}]

a(n) = A004526(n) - A068211(n) = A004526(n) - A006530(A000010(n)).

If n is a safe prime, then a(n)=0.

cp's OEIS Frontend

A070003 Numbers divisible by the square of their largest prime factor.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A035095 Smallest prime congruent to 1 (mod prime(n)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A070812 a(n) = phi(gpf(n)) - gpf(phi(n)) = A000010(A006530(n)) - A006530(A000010(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A070777 a(1) = 1; a(n) = (largest prime factor of n) - 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A065966 Numbers k such that phi(k) / 2 is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A070004 Numbers of the form 5*2^n or 5*3*2^n; a(n) = 5*A029744(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

A070004 Numbers of the form 52^n or 532^n; a(n) = 5A029744(n).