A007920 -id:A007920 - cp's OEIS frontend

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

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

A378457 Difference between n and the greatest prime power <= n, allowing 1.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 29 2024

nonn

Prime powers allowing 1 are listed by A000961.

			The greatest prime power <= 6 is 5, so a(6) = 1.

Sequences obtained by subtracting each term from n are placed in parentheses below.
For nonprime we have A010051 (almost) (A179278).
Subtracting from n gives (A031218).
For prime we have A064722 (A007917).
For perfect power we have A069584 (A081676).
For squarefree we have (A070321).
Adding one gives A276781.
For nonsquarefree we have (A378033).
For non perfect power we have (A378363).
For non prime power we have A378366 (A378367).
The opposite is A378370 = A377282-1.
A000015 gives the least prime power >= n.
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, weak version A007918.
Prime powers between primes: A053607, A080101, A304521, A366833, A377057.
Cf. A001597, A007920, A013632, A065514, A074984, A377051, A377054, A377281, A377289, A377468, A378357, A378371.

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

a(n) = n - A031218(n).

a(n) = A276781(n) - 1.

A171400 Minimal number of editing steps (delete, insert or substitute) to transform the binary representation of n into that of A007918(n), the least prime not less than n.

Original entry on oeis.org

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

Offset: 0

Reinhard Zumkeller, Dec 08 2009

Delete steps are not necessary;
a(n) = 0 iff n is prime: a(A000040(n))=0;
a(A171401(n)) = 1;
A171402 gives smallest numbers m such that a(m)=n: a(A171402(n))=n.

			n=14, A007918(14)=17: 14==1110->1100->1100->10001==17, 2 subst and 1 ins: a(14)=3;
n=15, A007918(15)=17: 15==1111->1011->1001->10001==17, 2 subst and 1 ins: a(15)=3;
n=16, A007918(16)=17: 16==10000->10001==17, 1 subst: a(16)=1, A171401(8)=16;
n=17, A007918(17)=17: no editing step: a(17)=0;
n=18, A007918(18)=19: 18==10010->10011==19, 1 subst: a(18)=1, A171401(9)=18.

R. Zumkeller, Table of n, a(n) for n = 0..2500
Michael Gilleland, Levenshtein Distance
Wikipedia, Levenshtein Distance

Cf. A007088, A007920.

a(n) = BinaryLevenshteinDistance(n, A007918(n)).

A378369 Distance between n and the least nonsquarefree number >= n.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 01 2024

nonn

All terms are 0, 1, 2, or 3 (cf. A078147).

Adding n to each term a(n) gives A120327.
Positions of 0 are A013929.
Positions of 1 are A373415.
Positions of 2 are A378458.
Positions of 3 are A007675.
Sequences obtained by adding n to each term are placed in parentheses below.
The version for primes is A007920 (A007918).
The version for perfect powers is A074984 (A377468).
The version for squarefree numbers is A081221 (A067535).
The version for non-perfect powers is A378357 (A378358).
The version for prime powers is A378370 (A000015).
The version for non prime powers is A378371 (A378372).
A005117 lists the squarefree numbers, first differences A076259.
A013929 lists the nonsquarefree numbers, first differences A078147.
A120992 gives run-lengths of squarefree numbers increasing by one.
Cf. A073247, A151800, A236575, A243348, A375707, A377046, A378033, A378039, A378086, A378373.

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

A072681 a(n) = (n - A007917(n)) * (A007918(n) - n).

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 3, 4, 3, 0, 1, 0, 3, 4, 3, 0, 1, 0, 3, 4, 3, 0, 5, 8, 9, 8, 5, 0, 1, 0, 5, 8, 9, 8, 5, 0, 3, 4, 3, 0, 1, 0, 3, 4, 3, 0, 5, 8, 9, 8, 5, 0, 5, 8, 9, 8, 5, 0, 1, 0, 5, 8, 9, 8, 5, 0, 3, 4, 3, 0, 1, 0, 5, 8, 9, 8, 5, 0, 3, 4, 3, 0, 5, 8, 9, 8, 5, 0, 7, 12, 15, 16, 15, 12, 7, 0, 3, 4, 3, 0, 1, 0

Offset: 2

Reinhard Zumkeller, Jul 01 2002

a(n)=0 iff n is prime.
Local maxima occur at interprimes: a(A024675(n)) = A074927(n+1). - Reinhard Zumkeller, Mar 04 2009
Expanding upon the maxima comment, repetitive subset triplets (like 3,4,3) of form (k,k+1,k) occur when the middle value is a square. - Bill McEachen, Apr 14 2025

Reinhard Zumkeller, Table of n, a(n) for n = 2..10000

Cf. A007917, A007918, A007920, A024675, A064722, A072680, A074927.

a[n_] := (n - NextPrime[n+1, -1])*(NextPrime[n] - n); Table[a[n], {n, 2, 103}] (* Jean-François Alcover, Jun 14 2013 *)

a(n) = A064722(n) * A007920(n).

a(n) = A064722(n) * (A072680(n) - A064722(n)).

A378366 Difference between n and the greatest non prime power <= n (allowing 1).

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Nov 29 2024

nonn

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, ...

Sequences obtained by subtracting each term from n are placed in parentheses below.
For nonprime we almost have A010051 (A179278).
For prime we have A064722 (A007917).
For perfect power we have A069584 (A081676).
For squarefree we have (A070321).
For prime power we have A378457 = A276781-1 (A031218).
For nonsquarefree we have (A378033).
For non perfect power we almost have A075802 (A378363).
Subtracting from n gives (A378367).
The opposite is A378371, adding n A378372.
A000015 gives the least prime power >= n (cf. A378370 = A377282 - 1).
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, weak version A007918.
Prime powers between primes: A053607, A080101, A304521, A366833, A377057.
Cf. A007916, A007920, A013632, A065514, A074984, A113646, A345531, A377051, A377054, A377281, A377289, A378357.

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

a(n) = n - A378367(n).

A096548 Difference between the smallest 10^n-digit prime and 10^(10^n-1).

Original entry on oeis.org

7, 289, 7, 33603, 309403, 593499

Offset: 1

Hugo Pfoertner, Jul 06 2004

Daniel Heuer found a(5) in 2004 by sieving up to 2^33 and then checking ~8000 candidates with pfgw-linux. Proving primality of 10^99999+309403 is beyond current (2004) technology.

a(6) was found by Kenneth Pedersen, Peter Kaiser, and Patrick De Geest. - Charles R Greathouse IV, Feb 11 2013

			a(1)=7 because the smallest ten-digit prime is 1000000007.
a(2)=289 because the smallest 100-digit prime is 10^99+289.

Prime Curios, 10000...33603 (10000-digits).
Chris K. Caldwell, The largest known primes.
Chris K. Caldwell, 10^999 + 7, related to a(3).
Chris K. Caldwell, 10^9999 + 33603, related to a(4).
factordb.com, 10^999 + 7, contains primality certificate related to a(3).
factordb.com, 10^9999 + 33603, contains primality certificate related to a(4).
Patrick De Geest, 10^999999 + y, history of a(6).
Henri Lifchitz, Renaud Lifchitz, Probable Primes Top 10000.
Henri Lifchitz, Renaud Lifchitz, 10^99999 + 309403, related to a(5).
Henri Lifchitz, Renaud Lifchitz, 10^999999 + 593499, related to a(6).
Hugo Pfoertner, Paul Underwood, Mike Oakes, Daniel Heuer, Smallest 100000-digit prime?, digest of 7 messages in primeform Yahoo group, Jul 8, 2004. [Cached copy]

Cf. A033873.

a(n) = nextprime(10^(10^n-1)) - 10^(10^n-1) = A007920(10^A002283(n)). - Jeppe Stig Nielsen, Jan 23 2021

A295335 a(n) = least k >= 0 such that n OR k is prime (where OR denotes the bitwise OR operator).

Original entry on oeis.org

2, 2, 0, 0, 1, 0, 1, 0, 3, 2, 1, 0, 1, 0, 17, 16, 1, 0, 1, 0, 3, 2, 1, 0, 5, 4, 5, 4, 1, 0, 1, 0, 5, 4, 9, 8, 1, 0, 9, 8, 1, 0, 1, 0, 3, 2, 1, 0, 5, 4, 9, 8, 1, 0, 73, 72, 3, 2, 1, 0, 1, 0, 65, 64, 3, 2, 1, 0, 3, 2, 1, 0, 1, 0, 5, 4, 3, 2, 1, 0, 3, 2, 1, 0, 43

Offset: 0

Rémy Sigrist, Nov 23 2017

See A295609 for the corresponding prime numbers.
We can show that this sequence is well defined by using Dirichlet's theorem on arithmetic progressions.
a(n) = 0 iff n is prime.
For any n >= 0, n AND a(n) = 0 (where AND denotes the bitwise AND operator).
If a(n) = x + y with x AND y = 0, then a(n + x) = y.
This sequence has similarities with A007920: here we check n OR k, there we check n + k.
See A295520 for the XOR variant.
For any k > 0, a(2^(6*k)-1) >= 2^(6*k) (hence the sequence is unbounded).

			For n = 42, 42 OR 0 = 42 is not prime, 42 OR 1 = 43 is prime, hence a(42) = 1.

Antti Karttunen, Table of n, a(n) for n = 0..8191
Antti Karttunen, Data supplement: n, a(n) computed for n = 0..65537
Rémy Sigrist, Scatterplot of the first 2^17 terms
Index entries for sequences related to binary expansion of n

Cf. A003986, A007920, A295520, A295609.

Table[Block[{k = 0}, While[! PrimeQ@ BitOr[k, n], k++]; k], {n, 0, 84}] (* Michael De Vlieger, Nov 26 2017 *)

avoid(n,i) = if (i, if (n%2, 2*avoid(n\2,i), 2*avoid(n\2,i\2)+(i%2)), 0) \\ (i+1)-th number k such that k AND n = 0
a(n) = for (i=0, oo, my (k=avoid(n,i)); if (isprime(n+k), return (k)))

For any k > 1, a(2*k+1) = a(2*k)-1.

A053785 Nextprime(n^4) - n^4.

Original entry on oeis.org

1, 1, 2, 1, 6, 1, 10, 3, 2, 7, 12, 7, 10, 15, 2, 1, 16, 11, 16, 1, 2, 3, 6, 1, 22, 3, 16, 1, 12, 13, 18, 7, 8, 1, 18, 11, 16, 7, 20, 21, 12, 25, 28, 3, 2, 1, 6, 1, 16, 9, 10, 43, 22, 1, 12, 1, 2, 25, 6, 19, 16, 3, 2, 43, 28, 5, 6, 3, 2, 31, 16, 7, 6, 1, 34, 3, 48, 5, 16, 1, 26, 1, 30, 47

Offset: 1

Enoch Haga, Mar 26 2000

			a(5)=6 because n^4=625 and next prime is 631; 631-625=6.

Cf. A000583, A053786.

Table[NextPrime[n^4]-n^4,{n,90}] (* Harvey P. Dale, Aug 27 2017 *)

a(n) = nextprime(n^4) - n^4; \\ Michel Marcus, Jun 06 2014

a(n) = A007920(n^4). - Michel Marcus, Jun 06 2014

A053787 Nextprime(n^5) - n^5.

Original entry on oeis.org

1, 5, 8, 7, 12, 13, 4, 3, 2, 3, 2, 7, 6, 17, 2, 7, 20, 11, 22, 3, 8, 7, 8, 13, 4, 3, 2, 9, 8, 7, 12, 35, 8, 3, 18, 5, 22, 33, 2, 7, 26, 5, 30, 35, 4, 13, 20, 13, 18, 17, 2, 15, 20, 13, 12, 5, 2, 9, 74, 11, 52, 47, 8, 3, 8, 53, 22, 3, 20, 27, 26, 5, 4, 53, 28, 7, 6, 19, 22, 17, 8, 31, 6, 17

Offset: 1

Enoch Haga, Mar 26 2000

			a(3)=8 because n^5=243 and next prime is 251; 251-243=8.

Cf. A000584, A053788.

a(n) = nextprime(n^5) - n^5; \\ Michel Marcus, Jun 06 2014

a(n) = A007920(n^5). - Michel Marcus, Jun 06 2014

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A378457 Difference between n and the greatest prime power <= n, allowing 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A171400 Minimal number of editing steps (delete, insert or substitute) to transform the binary representation of n into that of A007918(n), the least prime not less than n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A378369 Distance between n and the least nonsquarefree number >= n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A072681 a(n) = (n - A007917(n)) * (A007918(n) - n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A378366 Difference between n and the greatest non prime power <= n (allowing 1).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A096548 Difference between the smallest 10^n-digit prime and 10^(10^n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A295335 a(n) = least k >= 0 such that n OR k is prime (where OR denotes the bitwise OR operator).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A053785 Nextprime(n^4) - n^4.

Views