A013603 -id:A013603 - cp's OEIS frontend

A373125 Difference between 2^n and the least squarefree number >= 2^n.

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

Offset: 0

Gus Wiseman, May 28 2024

nonn

For prime instead of squarefree we have A092131, opposite A013603.
For primes instead of powers of 2: A240474, A240473, A112926, A112925.
Difference between 2^n and A372683(n).
The opposite is A373126, delta of A372889.
A005117 lists squarefree numbers, first differences A076259.
A053797 gives lengths of gaps between squarefree numbers.
A061398 counts squarefree numbers between primes (exclusive).
A070939 or (preferably) A029837 gives length of binary expansion.
A077643 counts squarefree terms between powers of 2, run-lengths of A372475.
A143658 counts squarefree numbers up to 2^n.
Cf. A372473 (firsts of A372472), A372541 (firsts of A372433).
For primes between powers of 2:
- sum A293697 (except initial terms)
- length A036378
- min A104080 or A014210, indices A372684 (firsts of A035100)
- max A014234, delta A013603
Cf. A010036, A029931, A049093-A049096, A077641, A372540, A373197, A373198.

Table[NestWhile[#+1&,2^n,!SquareFreeQ[#]&]-2^n,{n,0,100}]

a(n) = A372683(n)-2^n. - R. J. Mathar, May 31 2024

A092131 Distance from 2^n to the next prime.

Original entry on oeis.org

0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 17, 27, 3, 1, 29, 3, 21, 7, 17, 15, 9, 43, 35, 15, 29, 3, 11, 3, 11, 15, 17, 25, 53, 31, 9, 7, 23, 15, 27, 15, 29, 7, 59, 15, 5, 21, 69, 55, 21, 21, 5, 159, 3, 81, 9, 69, 131, 33, 15, 135, 29, 13, 131, 9, 3, 33, 29, 25, 11, 15, 29, 37, 33, 15, 11, 7, 23

Offset: 1

Helmut Richter (richter(AT)lrz.de), Mar 30 2004

Essentially the same as A013597. - T. D. Noe, Jul 17 2007
From Jianing Song, May 28 2024: (Start)
Not every odd number is present, as no term can be equal to a Sierpiński number (for example 78557); cf. A076336. See also A067760.
Conjecture: Every odd number which is not a Sierpiński number is a term. In other words, for every odd k which is not a Sierpiński number, there exists some n >= 1 such that 2^n + 1, 2^n + 3, ..., 2^n + (k-2) are all composite while 2^n + k is prime. (End)

			a(13)=17 because 2^13=8192 and the next prime is 8209=8192+17.

T. D. Noe, Table of n, a(n) for n=1..5000

Cf. A013597.
Equivalent sequence for previous prime: A013603.
Cf. A000079, A007920, A067760, A076336.

Join[{0},NextPrime[#]-#&/@(2^Range[2,80])] (* Harvey P. Dale, Jun 06 2012 *)

for(i=1,100,x=2^i;print1(nextprime(x)-x,","))

a(n) = nextprime(2^n) - 2^n.

a(n) = A007920(A000079(n)). - Michel Marcus, Oct 19 2022

A373126 Difference between 2^n and the greatest squarefree number <= 2^n.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, May 29 2024

nonn

			The greatest squarefree number <= 2^21 is 2097149, and 2^21 = 2097152, so a(21) = 3.

For prime instead of squarefree we have A013603, opposite A092131.
For primes instead of powers of 2: A240474, A240473, A112926, A112925.
Difference between 2^n and A372889.
The opposite is A373125, delta of A372683.
A005117 lists squarefree numbers, first differences A076259.
A053797 gives lengths of gaps between squarefree numbers.
A061398 counts squarefree numbers between primes (exclusive).
A070939 or (preferably) A029837 gives length of binary expansion.
A077643 counts squarefree terms between powers of 2, run-lengths of A372475.
A143658 counts squarefree numbers up to 2^n.
Cf. A372473 (firsts of A372472), A372541 (firsts of A372433).
For primes between powers of 2:
- sum A293697 (except initial terms)
- length A036378
- min A104080 or A014210, indices A372684 (firsts of A035100)
- max A014234
Cf. A010036, A029931, A046933, A049093-A049096, A077641, A372540, A373197.

Table[2^n-NestWhile[#-1&,2^n,!SquareFreeQ[#]&],{n,0,100}]

a(n) = 2^n-A372889(n). - R. J. Mathar, May 31 2024

A373123 Sum of all squarefree numbers from 2^(n-1) to 2^n - 1.

Original entry on oeis.org

1, 5, 18, 63, 218, 891, 3676, 15137, 60580, 238672, 953501, 3826167, 15308186, 61204878, 244709252, 979285522, 3917052950, 15664274802, 62663847447, 250662444349, 1002632090376, 4010544455838, 16042042419476, 64168305037147, 256675237863576

Offset: 1

Gus Wiseman, May 27 2024

nonn

			This is the sequence of row sums of A005117 treated as a triangle with row-lengths A077643:
   1
   2   3
   5   6   7
  10  11  13  14  15
  17  19  21  22  23  26  29  30  31
  33  34  35  37  38  39  41  42  43  46  47  51  53  55  57  58  59  61  62

Counting all numbers (not just squarefree) gives A010036.
For the sectioning of A005117:
Row-lengths are A077643, partial sums A143658.
First column is A372683, delta A373125, indices A372540, firsts of A372475.
Last column is A372889, delta A373126, indices A143658, diffs A077643.
For primes instead of powers of two:
- sum A373197
- length A373198 = A061398 - 1
- maxima A112925, opposite A112926
For prime instead of squarefree:
- sum A293697 (except initial terms)
- length A036378
- min A104080 or A014210, indices A372684 (firsts of A035100)
- max A014234, delta A013603
A000120 counts ones in binary expansion (binary weight), zeros A080791.
A005117 lists squarefree numbers, first differences A076259.
A030190 gives binary expansion, reversed A030308.
A070939 or (preferably) A029837 gives length of binary expansion.
Cf. A372473 (firsts of A372472), A372541 (firsts of A372433).
Cf. A029931, A048793, A049093, A049094, A059015, A069010, A077641.

Table[Total[Select[Range[2^(n-1),2^n-1],SquareFreeQ]],{n,10}]

a(n) = my(s=0); forsquarefree(i=2^(n-1), 2^n-1, s+=i[1]); s; \\ Michel Marcus, May 29 2024

A372889 Greatest squarefree number <= 2^n.

Original entry on oeis.org

1, 2, 3, 7, 15, 31, 62, 127, 255, 511, 1023, 2047, 4094, 8191, 16383, 32767, 65535, 131071, 262142, 524287, 1048574, 2097149, 4194303, 8388607, 16777214, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741822, 2147483647, 4294967295, 8589934591

Offset: 0

Gus Wiseman, May 27 2024

nonn

			The terms together with their binary expansions and binary indices begin:
      1:               1 ~ {1}
      2:              10 ~ {2}
      3:              11 ~ {1,2}
      7:             111 ~ {1,2,3}
     15:            1111 ~ {1,2,3,4}
     31:           11111 ~ {1,2,3,4,5}
     62:          111110 ~ {2,3,4,5,6}
    127:         1111111 ~ {1,2,3,4,5,6,7}
    255:        11111111 ~ {1,2,3,4,5,6,7,8}
    511:       111111111 ~ {1,2,3,4,5,6,7,8,9}
   1023:      1111111111 ~ {1,2,3,4,5,6,7,8,9,10}
   2047:     11111111111 ~ {1,2,3,4,5,6,7,8,9,10,11}
   4094:    111111111110 ~ {2,3,4,5,6,7,8,9,10,11,12}
   8191:   1111111111111 ~ {1,2,3,4,5,6,7,8,9,10,11,12,13}
  16383:  11111111111111 ~ {1,2,3,4,5,6,7,8,9,10,11,12,13,14}
  32767: 111111111111111 ~ {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

Positions of these terms in A005117 are A143658.
For prime instead of squarefree we have A014234, delta A013603.
For primes instead of powers of two we have A112925, opposite A112926.
Least squarefree number >= 2^n is A372683, delta A373125, indices A372540.
The opposite for prime instead of squarefree is A372684, firsts of A035100.
The delta (difference from 2^n) is A373126.
A000120 counts ones in binary expansion (binary weight), zeros A080791.
A005117 lists squarefree numbers, first differences A076259.
A030190 gives binary expansion, reversed A030308, length A070939 or A029837.
A061398 counts squarefree numbers between primes, exclusive.
A077643 counts squarefree terms between powers of 2, run-lengths of A372475.
Cf. A029931, A048793, A049093, A049094, A077641, A372433, A372472, A372473, A372541, A373197, A373198.

Table[NestWhile[#-1&,2^n,!SquareFreeQ[#]&],{n,0,15}]

a(n) = my(k=2^n); while (!issquarefree(k), k--); k; \\ Michel Marcus, May 29 2024

a(n) = A005117(A143658(n)).

a(n) = A070321(2^n). - R. J. Mathar, May 31 2024

A058249 (Smallest prime >= 2^n) - (largest prime <= 2^n).

Original entry on oeis.org

0, 2, 4, 4, 6, 6, 4, 6, 12, 10, 14, 6, 18, 30, 22, 16, 30, 8, 22, 10, 26, 18, 24, 46, 74, 20, 68, 60, 14, 38, 12, 20, 26, 66, 84, 36, 34, 52, 30, 102, 48, 26, 86, 24, 114, 36, 120, 80, 150, 82, 150, 68, 116, 192, 58, 86, 22, 96, 186, 126, 16, 192, 54, 72, 180, 14, 22, 56

Offset: 1

Labos Elemer, Dec 05 2000

nonn

This sequence gives the gap between consecutive primes on either side of 2^n. The average gap between primes near 2^n should be about g=n*log(2). Cramer's conjecture would allow gaps to be as large as about g^2. - T. D. Noe, Jul 17 2007

			n = 1: a(1) = 2 - 2 = 0,
n = 9: a(9) = 521 - 509 = 12.

Robert G. Wilson v, Table of n, a(n) for n = 1..10087 (first 5000 terms from T. D. Noe).

Cf. A013603, A013597, A014210, A014234, A038804.

a := n -> if n > 1 then nextprime(2^n)-prevprime(2^n) else 0 fi; [seq( a(i), i=1..256)]; # Maple's next/prevprime functions use strict inequalities and therefore would not yield the correct difference for n=1. Alternatively, a(n) = nextprime(2^n-1)-prevprime(2^n+1);

Prepend[NextPrime[#]-NextPrime[#,-1]&/@(2^Range[2,70]),0] (* Harvey P. Dale, Jan 25 2011 *)
Join[{0}, Table[NextPrime[2^n] - NextPrime[2^n, -1], {n, 2, 70}]]

a(n)=nextprime(2^n)-precprime(2^n) \\ Charles R Greathouse IV, Sep 20 2016

a(n) = A014210(n) - A014234(n) = A013603(n) + A013597(n).

Edited by M. F. Hasler, Feb 14 2017

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

Original entry on oeis.org

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

A057821 a(n) is the least nonnegative integer k such that 2^n - k is a safe prime.

Original entry on oeis.org

1, 5, 9, 5, 21, 29, 9, 5, 9, 17, 45, 161, 165, 269, 285, 17, 45, 233, 9, 17, 321, 317, 633, 677, 405, 437, 189, 1385, 69, 209, 9, 641, 849, 137, 45, 401, 381, 437, 1965, 2201, 741, 1493, 573, 857, 1485, 5297, 2709, 161, 465, 473, 1269, 4805, 789

Offset: 3

Warren D. Smith, Nov 23 2000

nonn

Previous name was: "Useful safe primes: a(n) = least nonnegative integer k such that 2^n - k is prime and (2^n-k-1)/2 is also prime". The resulting sequence of 2^n-k terms: 7, 11, 23, 59, 107, ..., are thus the largest safe primes smaller than 2^n (A243916), a subsequence of A005385. - Michel Marcus, Jan 08 2014

Mark Andreas, Table of n, a(n) for n = 3..5120 (first 3070 terms from Artsiom Palkounikau)

Cf. A005385, A013603, A243916.

a(n) = {my(k=0); until (isprime(2^n-k) && isprime((2^n-k-1)/2), k++); return (k);} \\ Michel Marcus, Jun 29 2013

from sympy import isprime
def a(n):
    k=0
    while True:
        k+=1
        if isprime(2**n - k) and isprime((2**n - k - 1)//2): return k
print([a(i) for i in range(3, 21)]) # Indranil Ghosh, Jun 12 2017, after PARI code by Michel Marcus

A058220 Ultra-useful primes: smallest k such that 2^(2^n) - k is prime.

Original entry on oeis.org

1, 3, 5, 15, 5, 59, 159, 189, 569, 105, 1557, 2549, 2439, 13797, 25353, 5627, 24317, 231425, 164073

Offset: 1

Warren D. Smith, Nov 30 2000

2^(2^16) - 5627 was found by Joel Levy in Feb 2004. - Donovan Johnson, Sep 13 2008

Corresponding numbers to entries a(1) to a(12) are proven primes, higher terms are probable primes. - Matthias Baur, Mar 17 2020

			For n = 3, we see that 2^(2^3) = 2^8 = 256, which is clearly not prime.
256 - 1 = 255 = 3 * 5 * 17, so a(3) is not 1.
256 - 2 = 254 = 2 * 127, so a(3) is not 2 either.
256 - 3 = 253 = 11 * 23, so a(3) is not 3 either.
256 - 5 = 251, which is prime, so a(3) = 5.

Rosetta Code, Ultra-useful primes.

Cf. A001146, A013603, A058221.

ultraUseful[n_] := Module[{x = 2^(2^n)}, x - NextPrime[x, -1]]; Array[ultraUseful, 17] (* Harvey P. Dale, Jun 04 2011 *)

a(n) = A013603(2^n). - Jinyuan Wang, Jun 06 2020

a(16)-a(17) from Donovan Johnson, Sep 13 2008
a(18) from Matthias Baur, Mar 17 2020
a(19) from Matthias Baur, Apr 04 2020

A059959 Distance of 2^n from its nearest prime neighbor and in case of a tie, choose the smaller.

Original entry on oeis.org

-1, 0, 1, 1, -1, 1, 3, 1, -1, 3, 3, -5, 3, 1, 3, -3, -1, 1, -3, 1, 3, 9, 3, -9, 3, -35, 5, -29, -3, 3, -3, 1, 5, 9, -25, 31, 5, -9, -7, 7, -15, 21, 11, -29, -7, 55, -15, -5, -21, -69, 27, -21, -21, -5, 33, -3, 5, -9, 27, 55, -33, 1, 57, 25, -13, 49, 5, -3, 23, 19, -25, -11, -15, -29, 35, -33, 15, -11, -7, -23, -13, -17, -9, 55, -3, 19

Offset: 0

Labos Elemer, Mar 02 2001

sign

			n=19, 2^19=524288, prevprime(524288)=524287, nextprime(524288)=524309, so min{21,1}=1=a(19).

Robert G. Wilson v, Table of n, a(n) for n = 0..10000 (terms 0-4500 from Giovanni Resta)

Cf. A000079, A117387, A013597, A013603, A014210, A014234, A058249.

with(numtheory): [seq(min(nextprime(2^i)-2^i, 2^i-prevprime(2^i)), i=2..100)];

f[n_] := Block[{k = 0}, While[ !PrimeQ[2^n -k] && !PrimeQ[2^n +k], k++]; If[ PrimeQ[2^n -k], k, -k]]; Array[f, 70, 0] (* Robert G. Wilson v, Mar 14 2006 and modified Jan 12 2024 *)

a(n) = A000079(n) - A117387(n).

Signs added by Robert G. Wilson v, Mar 14 2006

cp's OEIS Frontend

A373125 Difference between 2^n and the least squarefree number >= 2^n.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A092131 Distance from 2^n to the next prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A373126 Difference between 2^n and the greatest squarefree number <= 2^n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A373123 Sum of all squarefree numbers from 2^(n-1) to 2^n - 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

A372889 Greatest squarefree number <= 2^n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A058249 (Smallest prime >= 2^n) - (largest prime <= 2^n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Python

Formula

A057821 a(n) is the least nonnegative integer k such that 2^n - k is a safe prime.

Views

Author

Keywords

Comments

Links

Crossrefs