A007918 -id:A007918 - cp's OEIS frontend

A378357 Distance from n to the least non perfect power >= n.

1, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0

Offset: 1

Gus Wiseman, Nov 24 2024

nonn

Perfect powers (A001597) are 1 and numbers with a proper integer root, complement A007916.

All terms are <= 2 because the only adjacent perfect powers are 8 and 9.

The version for prime numbers is A007920, subtraction of A159477 or A007918.
The version for perfect powers is A074984, subtraction of A377468.
The version for squarefree numbers is A081221, subtraction of A067535.
Subtracting from n gives A378358, opposite A378363.
The opposite version is A378364.
The version for nonsquarefree numbers is A378369, subtraction of A120327.
The version for prime powers is A378370, subtraction of A000015.
The version for non prime powers is A378371, subtraction of A378372.
The version for composite numbers is A378456, subtraction of A113646.
A000961 lists the powers of primes, differences A057820.
A001597 lists the perfect powers, differences A053289, seconds A376559.
A007916 lists the non perfect powers, differences A375706, seconds A376562.
A069623 counts perfect powers <= n.
A076411 counts perfect powers < n.
A377432 counts perfect powers between primes, zeros A377436.
Cf. A013597, A013603, A013632, A031218, A045542, A052410, A081676, A131605, A188951, A216765, A375702, A375736.

perpowQ[n_]:=n==1||GCD@@FactorInteger[n][[All,2]]>1;
Table[NestWhile[#+1&,n,#>1&&perpowQ[#]&]-n,{n,100}]

from sympy import perfect_power
def A378357(n): return 0 if n>1 and perfect_power(n)==False else 1 if perfect_power(n+1)==False else 2 # Chai Wah Wu, Nov 27 2024

a(n) = n - A378358(n).

A066169 Least k such that phi(k) >= n.

Original entry on oeis.org

1, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13, 17, 17, 17, 17, 19, 19, 23, 23, 23, 23, 29, 29, 29, 29, 29, 29, 31, 31, 37, 37, 37, 37, 37, 37, 41, 41, 41, 41, 43, 43, 47, 47, 47, 47, 53, 53, 53, 53, 53, 53, 59, 59, 59, 59, 59, 59, 61, 61, 67, 67, 67, 67, 67, 67, 71, 71, 71, 71, 73

Offset: 1

Joseph L. Pe, Dec 13 2001

Thinking of n as time, a(n) represents the first time phi catches up with i(n), where i is the identity function. a(n) - n can be seen as the lag of phi behind i at time n. The sequence of these lags begins 0 1 2 1 2 1 4 3 2 1 2 1 4 3 2 1 2 1 4 3 2 1

a(n) is the smallest number for which the reduced residue system (=RRS(a(n))) contains {1,2,...,n} as a subset; a(m) jumps at a(p)-1 and a(p) from value of p to nextprime(p); a(x)=p(n) holds {p(n-1)...p(n)-1}; p(n) is repeated p(n)-p(n-1) times. For n > 1, a(n) = p(Pi(n)+1), while a(1)=1. - Labos Elemer, May 14 2003

			a(5) = 7 since phi(7) = 6 is at least 5 and 7 is the smallest k satisfying phi(k) is greater than or equal to 5.

Harry J. Smith, Table of n, a(n) for n = 1..1000

Cf. A000040, A000720, A057237.

a(1)=1; Table[Prime[PrimePi[w]+1], {w, 1, 100}]

{ for (n=1, 1000, k=1; while (eulerphi(k) < n, k++); write("b066169.txt", n, " ", k) ) } \\ Harry J. Smith, Feb 04 2010

print1(n=1);n=2;forprime(p=3,31,while(n++<=p,print1(", "p));n--) \\ Charles R Greathouse IV, Oct 31 2011

a(1) = 1 a(n) = p(s+1) for n in [p(s), p(s+1) - 1], where p(s) denotes the s-th prime.
For n > 1 a(n) = A007918(n+1). - Benoit Cloitre, May 04 2002
For n > 1, a(n) = A000040(A000720(n)+1), while a(1)=1. - Labos Elemer, May 14 2003

More terms from Benoit Cloitre, May 04 2002

A085420 For each n, let p(n,b) be the smallest prime in the arithmetic progression k*n+b, with k > 0. Then a(n) = max(p(n,b)) with 0 < b < n and gcd(b,n) = 1.

Original entry on oeis.org

2, 3, 7, 7, 19, 11, 29, 23, 43, 19, 71, 23, 103, 53, 43, 43, 103, 53, 191, 59, 97, 79, 233, 73, 269, 103, 173, 83, 317, 79, 577, 151, 227, 193, 239, 157, 439, 191, 233, 157, 587, 107, 467, 257, 389, 307, 967, 191, 613, 269, 421, 601, 659, 199, 353, 233, 433, 317, 709

Offset: 1

T. D. Noe, Jun 29 2003

nonn

Linnik proved that there are n0 and L such that a(n) < n^L for all n > n0. It has been conjectured that a(n) < n^2. The sequence A034694 has the primes p(n,1).

a(n) is also the maximum term in row n of A060940, which defines a(1). A007918(n+1) is the minimum term in row n of A060940. - Seiichi Manyama, Apr 02 2018

			a(5) = 19 because p(5,1) = 11, p(5,2) = 7, p(5,3) = 13 and p(5,4) = 19.

P. Ribenboim, The New Book of Prime Number Records, Springer, 1996, pp. 277-284.

T. D. Noe, Table of n, a(n) for n = 1..10000 (corrected by Michel Marcus, Jan 19 2019)
A. Granville, Least primes in arithmetic progressions, Théorie des nombres / Number Theory (ed. J. M. De Koninck & C. Levesque), (de Gruyter, New York, 1989), 306-321.
Eric Weisstein's World of Mathematics, Linnik's Theorem

A038026 is a lower bound.

Cf. A034694.

minP[n_, a_] := Module[{k, p}, If[GCD[n, a]>1, p=0, k=1; While[ !PrimeQ[k*n+a], k++ ]; p=k*n+a]; p]; Table[Max[Table[minP[n, i], {i, n-1}]], {n, 2, 100}]

p(n,b)=while(!isprime(b+=n),); ba(n)=my(t=p(n,1));for(b=2,n-1,if(gcd(n,b)==1,t=max(t,p(n,b))));t \\ Charles R Greathouse IV, Sep 08 2012

a(1) defined via A060940 by Seiichi Manyama, Apr 02 2018

A378358 Least non-perfect-power >= n.

Original entry on oeis.org

2, 2, 3, 5, 5, 6, 7, 10, 10, 10, 11, 12, 13, 14, 15, 17, 17, 18, 19, 20, 21, 22, 23, 24, 26, 26, 28, 28, 29, 30, 31, 33, 33, 34, 35, 37, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 50, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 65, 66, 67

Offset: 1

Gus Wiseman, Nov 24 2024

nonn

Perfect-powers (A001597) are 1 and numbers with a proper integer root, complement A007916.

The version for prime-powers is A000015, for non-prime-powers A378372.
The union is A007916, complement A001597.
The version for nonsquarefree numbers is A067535, negative A120327 (subtract A378369).
The version for composite numbers is A113646.
The version for prime numbers is A159477.
The run-lengths are A375706.
Terms appearing only once are A375738, multiple times A375703.
The version for perfect-powers is A377468.
Subtracting from n gives A378357.
The opposite version is A378363, for perfect-powers A081676.
A000040 lists the primes, differences A001223.
A000961 lists the powers of primes, differences A057820.
A001597 lists the perfect-powers, differences A053289.
A007916 lists the non-perfect-powers, differences A375706.
A069623 counts perfect-powers <= n.
A076411 counts perfect-powers < n.
A131605 lists perfect-powers that are not prime-powers.
A377432 counts perfect-powers between primes, zeros A377436.
Cf. A007918, A014210, A031218, A045542, A052410, A065514, A070321, A076412, A188951, A216765, A345531, A378033.

perpowQ[n_]:=n==1||GCD@@FactorInteger[n][[All,2]]>1;
Table[NestWhile[#+1&,n,perpowQ[#]&],{n,100}]

from sympy import mobius, integer_nthroot
def A378358(n):
    def f(x): return int(1-sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))
    a = max(1,n-f(n-1))
    m, k = a, f(a)+a
    while m != k: m, k = k, f(k)+a
    return m # Chai Wah Wu, Nov 26 2024

from sympy import perfect_power
def A378358(n): return n if n>1 and perfect_power(n)==False else n+1 if perfect_power(n+1)==False else n+2 # Chai Wah Wu, Nov 27 2024

a(n) = n - A378357(n).

A378370 Distance between n and the least prime power >= n, allowing 1.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 0, 0, 1, 0, 3, 2, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 4, 3, 2, 1, 0, 3, 2, 1, 0, 1, 0, 3, 2, 1, 0, 1, 0, 3, 2, 1, 0, 5, 4, 3, 2, 1, 0, 1, 0, 2, 1, 0, 2, 1, 0, 3, 2, 1, 0, 1, 0, 5, 4, 3, 2, 1, 0, 1, 0, 1, 0, 5, 4, 3, 2

Offset: 1

Gus Wiseman, Nov 27 2024

nonn

Prime powers allowing 1 are listed by A000961.

Sequences obtained by adding n to each term are placed in parentheses below.
For prime instead of prime power we have A007920 (A007918), strict A013632.
For perfect power we have A074984 (A377468), opposite A069584 (A081676).
For squarefree we have A081221 (A067535).
The restriction to the prime numbers is A377281 (A345531).
The strict version is A377282 = a(n) + 1.
For non prime power instead of prime power we have A378371 (A378372).
The opposite version is A378457, strict A276781.
A000015 gives the least prime power >= n, opposite A031218.
A000040 lists the primes, differences A001223.
A000961 and A246655 list the prime powers, differences A057820.
A024619 and A361102 list the non prime powers, differences A375708 and A375735.
A151800 gives the least prime > n.
Prime-powers between primes: A053607, A080101, A304521, A366833, A377057.
Cf. A001597, A053707, A065514, A065890, A343249, A376596, A376597, A377051, A377054, A377289, A377781.

Table[NestWhile[#+1&,n,#>1&&!PrimePowerQ[#]&]-n,{n,100}]

a(n) = A000015(n) - n.

a(n) = A377282(n - 1) - 1 for n > 1.

A062851 Number of k such that 1 < k < n X n and k not of the form ij for 1 <= {i, j} <= n.

Original entry on oeis.org

0, 1, 3, 7, 11, 18, 24, 34, 45, 58, 68, 85, 97, 116, 136, 159, 175, 201, 219, 248, 277, 308, 330, 367, 400, 437, 475, 517, 545, 592, 622, 670, 717, 766, 815, 873, 909, 964, 1020, 1083, 1123, 1189, 1231, 1298, 1366, 1433, 1479, 1557, 1623, 1700, 1774, 1854

Offset: 1

Ron A. Lalonde (ronronronlalonde(AT)hotmail.com), Jun 25 2001

nonn

Smallest k for given n is given by A007918, largest by A005563 (except for some initial terms).

			a(4)=7 because there are 9 unique products in the 4 X 4 multiplication table (1 2 3 4 6 8 9 12 16), which excludes 7 non-product integers within the range 1 to 16 (5 7 10 11 13 14 15).

a(n) = n^2 - A027424.

Cf. A027424, A062854, A062855, A062856, A062857, A062859.

def A062851(n): return n**2-len({i*j for i in range(1,n+1) for j in range(1,i+1)}) # Chai Wah Wu, Oct 13 2023

A138754 a(n) = PrimePi(A138751(n)) - a variation of the Collatz (3n+1) map.

Original entry on oeis.org

1, 4, 2, 7, 4, 10, 5, 13, 6, 7, 19, 22, 9, 24, 10, 10, 11, 31, 33, 12, 35, 38, 14, 15, 45, 16, 47, 17, 48, 17, 55, 19, 20, 60, 22, 63, 66, 67, 24, 24, 25, 73, 25, 77, 26, 79, 83, 87, 31, 89, 31, 31, 93, 31, 32, 33, 33, 101, 102, 35, 104, 35, 113, 37, 115, 38, 122, 123, 41, 126

Offset: 1

M. F. Hasler, Apr 01 2008

This map is a variation of the Collatz (or 3n+1) map:
Instead of considering the parity of the number, we look at prime(n) mod 3 to decide if this prime should be halved or doubled, before going to the next prime (A007918) and finally back to the positive integers via PrimePi (A000720).
Exactly as for the Collatz (3n+1) map (defined on nonnegative integers), the first element for which it is defined is its only fixed point, and all other starting values seem to end up in a cycle of length 3, here: 4 -> 7 -> 5 -> 4.
Except for p=3, no prime yields a prime result under the map A138750 (as can be seen using p=6k+1 or p=6k-1). Therefore instead of applying primepi() after nextprime(), one could also simply use 1+primepi().
The prime p=3 is also the only case where n == 2 (mod 3) is not equivalent to n != 1 (mod 3). It might have been a better choice to define A138750(x)=2x if x == 1 (mod 3), ceiling(x/2) otherwise. But since here it makes only a difference for p=3, we use the original definition (cf. A124123).

			a(4) = 7 since prime(4) = 7 == 1 (mod 3), thus A138750(7) = 2*7 = 14, nextprime(14) = 17, PrimePi(17) = 7 (i.e., 17 is the 7th prime).
a(5) = 4 since prime(5) = 11 == 2 (mod 3), thus A138750(11) = ceiling(11/2) = 6, nextprime(6) = 7, PrimePi(7) = 4 (i.e., 7 is the 4th prime).

Cf. A124123, A138750-A138753, A000040, A000720, A007918.

A138754[n_]:=With[{p=Prime[n]},PrimePi[NextPrime[If[Mod[p,3]==2,p/2,2p]]]];Array[A138754,100] (* Paolo Xausa, Jul 28 2023 *)

A138754(n)=primepi(A138751(n)) /* see there */

a(n) = A000720(A138751(n)) = A000720(A007918(A138750(A000040(n)))).

A378363 Greatest number <= n that is 1 or not a perfect-power.

Original entry on oeis.org

1, 2, 3, 3, 5, 6, 7, 7, 7, 10, 11, 12, 13, 14, 15, 15, 17, 18, 19, 20, 21, 22, 23, 24, 24, 26, 26, 28, 29, 30, 31, 31, 33, 34, 35, 35, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 48, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 63, 65, 66, 67

Offset: 1

Gus Wiseman, Nov 24 2024

Perfect-powers (A001597) are 1 and numbers with a proper integer root, complement A007916.

			In the non-perfect-powers ... 5, 6, 7, 10, 11 ... the greatest term <= 8 is 7, so a(8) = 7.

The union is A007916, complement A001597.
The version for prime numbers is A007917 or A151799, opposite A159477.
The version for prime-powers is A031218, opposite A000015.
The version for squarefree numbers is A067535, opposite A070321.
The version for perfect-powers is A081676, opposite A377468.
The version for composite numbers is A179278, opposite A113646.
Terms appearing multiple times are A375704, opposite A375703.
The run-lengths are A375706.
Terms appearing only once are A375739, opposite A375738.
The version for nonsquarefree numbers is A378033, opposite A120327.
The opposite version is A378358.
Subtracting n gives A378364, opposite A378357.
The version for non-prime-powers is A378367 (subtracted A378371), opposite A378372.
A000040 lists the primes, differences A001223.
A000961 lists the powers of primes, differences A057820.
A001597 lists the perfect-powers, differences A053289.
A007916 lists the non-perfect-powers, differences A375706.
A069623 counts perfect-powers <= n.
A076411 counts perfect-powers < n.
A131605 lists perfect-powers that are not prime-powers.
A377432 counts perfect-powers between primes, zeros A377436.
Cf. A007918, A014210, A014234, A045542, A052410, A065514, A076412, A162966, A188951, A345531.

perpowQ[n_]:=n==1||GCD@@FactorInteger[n][[All,2]]>1;
Table[NestWhile[#-1&,n,#>1&&perpowQ[#]&],{n,100}]

from sympy import mobius, integer_nthroot
def A378363(n):
    def f(x): return int(1-sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))
    a = n-f(n)
    m, k = a, f(a)+a
    while m != k: m, k = k, f(k)+a
    return m # Chai Wah Wu, Nov 26 2024

A378367 Greatest non prime power <= n, allowing 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 6, 6, 6, 6, 10, 10, 12, 12, 14, 15, 15, 15, 18, 18, 20, 21, 22, 22, 24, 24, 26, 26, 28, 28, 30, 30, 30, 33, 34, 35, 36, 36, 38, 39, 40, 40, 42, 42, 44, 45, 46, 46, 48, 48, 50, 51, 52, 52, 54, 55, 56, 57, 58, 58, 60, 60, 62, 63, 63, 65, 66, 66

Offset: 1

Gus Wiseman, Nov 29 2024

Non prime powers allowing 1 (A361102) are numbers that are not a prime power (A246655), namely 1, 6, 10, 12, 14, 15, 18, 20, 21, 22, 24, ...

			The greatest non prime power <= 7 is 6, so a(7) = 6.

Sequences obtained by subtracting each term from n are placed in parentheses below.
For prime we have A007917 (A064722).
For nonprime we have A179278 (A010051 almost).
For perfect power we have A081676 (A069584).
For squarefree we have A070321.
For nonsquarefree we have A378033.
For non perfect power we have A378363.
The opposite is A378372, subtracting n A378371.
For prime power we have A031218 (A276781 - 1).
Subtracting from n gives (A378366).
A000015 gives the least prime power >= n (A378370).
A000040 lists the primes, differences A001223.
A000961 and A246655 list the prime powers, differences A057820.
A024619 and A361102 list the non prime powers, differences A375708 and A375735.
A151800 gives the least prime > n (A013632), weak version A007918 (A007920).
Prime powers between primes: A053607, A080101, A304521, A366833, A377057.
Cf. A007916, A065514, A113646, A345531 (A377281), A377051, A377054, A377282, A377468 (A074984), A378358, A378457.
Cf. A356068.

Table[NestWhile[#-1&,n,PrimePowerQ[#]&],{n,100}]

a(n) = n - A378366(n).

a(n) = A361102(A356068(n)). - Ridouane Oudra, Aug 22 2025

A030664 Product of largest prime <= n and smallest prime >= n.

Original entry on oeis.org

1, 1, 4, 9, 15, 25, 35, 49, 77, 77, 77, 121, 143, 169, 221, 221, 221, 289, 323, 361, 437, 437, 437, 529, 667, 667, 667, 667, 667, 841, 899, 961, 1147, 1147, 1147, 1147, 1147, 1369, 1517, 1517, 1517, 1681, 1763, 1849, 2021, 2021, 2021, 2209, 2491, 2491, 2491

Offset: 0

N. J. A. Sloane

Symmetrical about zero, a(n)=a(-n) if n>1, if negative primes are recognized. - Robert G. Wilson v, Feb 28 2011

Iff n is a prime then a(n)=n^2, otherwise a(n) is a semiprime. - Robert G. Wilson v, Feb 28 2011

T. D. Noe, Table of n, a(n) for n = 0..1000

Cf. A000040, A013638, A006094, A001248.

Cf. A007917, A007918, A013638.

a030664 n = a007917 n * a007918 n -- Reinhard Zumkeller, May 22 2015, Feb 24 2011

f[n_] := If[Abs[n] < 2, 1, NextPrime[n + 1, -1] NextPrime[n - 1]]; Array[f, 51, 0] (* Robert G. Wilson v, Feb 28 2011 *)

numlib::prevprime(i)*nextprime(i) $ i = 0..50 // Zerinvary Lajos, Feb 26 2007

a(n) = if (n < 2, 1, precprime(n)*nextprime(n)); \\ Michel Marcus, Mar 21 2015

For n > 1: a(n) = A007917(n)*A007918(n). - Reinhard Zumkeller, May 22 2015

More terms from Erich Friedman

cp's OEIS Frontend

A378357 Distance from n to the least non perfect power >= n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Python

Formula

A066169 Least k such that phi(k) >= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A085420 For each n, let p(n,b) be the smallest prime in the arithmetic progression k*n+b, with k > 0. Then a(n) = max(p(n,b)) with 0 < b < n and gcd(b,n) = 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A378358 Least non-perfect-power >= n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Python

Python

Formula

A378370 Distance between n and the least prime power >= n, allowing 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A062851 Number of k such that 1 < k < n X n and k not of the form ij for 1 <= {i, j} <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

A138754 a(n) = PrimePi(A138751(n)) - a variation of the Collatz (3n+1) map.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A378363 Greatest number <= n that is 1 or not a perfect-power.