A014234 -id:A014234 - cp's OEIS frontend

A372889 Greatest squarefree number <= 2^n.

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

A377467 Number of perfect-powers x in the range 2^n < x < 2^(n+1).

Original entry on oeis.org

0, 0, 0, 1, 2, 2, 4, 6, 7, 10, 15, 23, 31, 41, 60, 81, 117, 165, 230, 321, 452, 634, 891, 1252, 1766, 2486, 3504, 4935, 6958, 9815, 13849, 19537, 27577, 38932, 54971, 77640, 109667, 154921, 218878, 309276, 437046, 617657, 872967, 1233895, 1744152, 2465546, 3485477

Offset: 0

Gus Wiseman, Nov 04 2024

nonn

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

Also the number of perfect-powers, except for powers of 2, with n bits.

			The perfect-powers in each prescribed range (rows):
    .
    .
    .
    9
   25   27
   36   49
   81  100  121  125
  144  169  196  216  225  243
  289  324  343  361  400  441  484
  529  576  625  676  729  784  841  900  961 1000
The binary expansions for n >= 3 (columns):
    1001  11001  100100  1010001  10010000  100100001
          11011  110001  1100100  10101001  101000100
                         1111001  11000100  101010111
                         1111101  11011000  101101001
                                  11100001  110010000
                                  11110011  110111001
                                            111100100

The version for squarefree numbers is A077643.
The version for prime-powers is A244508.
For primes instead of powers of 2 we have A377432, zeros A377436.
Including powers of 2 in the range gives A377435.
The version for non-perfect-powers is A377701.
The union of all numbers counted is A377702.
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.
A081676 gives the greatest perfect-power <= n.
A131605 lists perfect-powers that are not prime-powers.
A377468 gives the least perfect-power > n.
Cf. A000015, A013597, A014210, A014234, A023055, A031218, A045542, A052410, A065514, A069623, A216765, A246655, A345531.

perpowQ[n_]:=n==1||GCD@@FactorInteger[n][[All,2]]>1;
Table[Length[Select[Range[2^n+1,2^(n+1)-1],perpowQ]],{n,0,15}]

from sympy import mobius, integer_nthroot
def A377467(n):
    def f(x): return int(1-sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))
    return f((1<Chai Wah Wu, Nov 05 2024

For n != 1, a(n) = A377435(n) - 1.

a(26)-a(46) from Chai Wah Wu, Nov 05 2024

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

A120274 Largest prime factor of the odd Catalan number A038003(n).

Original entry on oeis.org

5, 13, 29, 61, 113, 251, 509, 1021, 2039, 4093, 8179, 16381, 32749, 65521, 131063, 262139, 524269, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909, 1073741789, 2147483629

Offset: 2

Alexander Adamchuk, Jul 04 2006, Jul 13 2006, Jul 26 2006

nonn

For n=6 a(n) differs from the largest prime factor of (2*(2^n-1))! = A028367[n].
A038003[n] = binomial(2^(n+1)-2, 2^n-1)/(2^n).
The numbers of distinct prime factors of the odd Catalan numbers A038003(n): 3, 6, 11, 20, 36, 64, 117, 209, 381, 699, 1291, 2387, 4445, 8317, 15645, 29494, ..., . - Robert G. Wilson v, May 11 2007

			a(2) = 5 because A038003[2] = 5.
a(3) = 13 because A038003[3] = 429 = 3*11*13.

Harvey P. Dale, Table of n, a(n) for n = 2..1000

Cf. A038003, A000108, A014234, A028367.

(* first do *) Needs["DiscreteMath`CombinatorialFunctions`"] (* then *) f[n_] := FactorInteger[CatalanNumber[2^n - 1]][[ -1, 1]]; lst = {}; Do[ Append[lst, f@n], {n, 2, 20}]; lst (* Or *) (* Robert G. Wilson v, May 11 2007 *)
PrevPrim[n_] := Block[{k = n - 1}, While[ ! PrimeQ@k, k-- ]; k]; Table[ PrevPrim[2^n - 2], {n, 3, 32}] (* Robert G. Wilson v, May 11 2007 *)
Table[NextPrime[2^n-2,-1],{n,3,50}] (* Harvey P. Dale, Apr 22 2018 *)

Equals greatest prime less than 2^n-2. - Robert G. Wilson v, May 11 2007

More terms from Robert G. Wilson v, May 11 2007

Edited by N. J. A. Sloane, Oct 15 2007

A102644 A006530(x)=2 is a local minimum if x=2^n. Running downward with argument x started at 2^n, the largest prime divisor should increase. The value of first peak is a(n).

Original entry on oeis.org

2, 3, 7, 13, 31, 61, 127, 127, 73, 1021, 89, 4093, 8191, 16381, 151, 257, 131071, 131071, 524287, 1048573, 337, 683, 178481, 16777213, 1801, 8191, 262657, 1877171, 2089, 46684427, 2147483647, 2147483647, 599479, 3360037, 6871947673, 283007

Offset: 1

Labos Elemer, Jan 21 2005

nonn

We may call these terms "downward-zenith-primes" belonging to 2^n-s. They do not exceed previous-primes before 2^n [A014234(n)].

			n=20: 2^20=1048576; the largest prime divisors for arguments if running downward from 2^20 are as follows: {2,41,524287,1048573,73}.
The first lower peak before argument 2^20=1048576 is a(20)=1048573.
n=1: a(1)=2 the peak equals the central value because there are no prime divisors>0 below n=2^1=2.

Michael De Vlieger, Table of n, a(n) for n = 1..150

Cf. A006530, A102640, A102641, A102642, A102643, A014234.

Table[2 + Total@ TakeWhile[Differences@ Map[FactorInteger[#][[-1, 1]] &,
TakeWhile[Range[2^n, 2^n - 20, -1], # > 0 &]], # > 0 &], {n, 36}] (* Michael De Vlieger, Jul 31 2017 *)

A377702 Perfect-powers except for powers of 2.

Original entry on oeis.org

9, 25, 27, 36, 49, 81, 100, 121, 125, 144, 169, 196, 216, 225, 243, 289, 324, 343, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1000, 1089, 1156, 1225, 1296, 1331, 1369, 1444, 1521, 1600, 1681, 1728, 1764, 1849, 1936, 2025, 2116, 2187, 2197

Offset: 1

Gus Wiseman, Nov 05 2024

nonn

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

			The terms together with their prime indices begin:
     9: {2,2}
    25: {3,3}
    27: {2,2,2}
    36: {1,1,2,2}
    49: {4,4}
    81: {2,2,2,2}
   100: {1,1,3,3}
   121: {5,5}
   125: {3,3,3}
   144: {1,1,1,1,2,2}
   169: {6,6}
   196: {1,1,4,4}
   216: {1,1,1,2,2,2}
   225: {2,2,3,3}
   243: {2,2,2,2,2}
   289: {7,7}
   324: {1,1,2,2,2,2}

Including the powers of 2 gives A001597, counted by A377435.
For prime-powers we have A061345.
These terms are counted by A377467, for non-perfect-powers A377701.
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.
A081676 gives the greatest perfect-power <= n.
A131605 lists perfect-powers that are not prime-powers.
A188951 counts perfect-powers less than 2^n.
A377468 gives the least perfect-power > n.
Cf. A014210, A014234, A023055, A045542, A052410, A065514, A069623, A246655, A304521, A336416, A345531, A366833.

Select[Range[1000],GCD@@FactorInteger[#][[All,2]]>1&&!IntegerQ[Log[2,#]]&]

from sympy import mobius, integer_nthroot
def A377702(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return int(n-2+x+(l:=x.bit_length())+sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,l)))
    return bisection(f,n+1,n+1) # Chai Wah Wu, Nov 06 2024

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

A104089 Largest prime <= 4^n.

Original entry on oeis.org

3, 13, 61, 251, 1021, 4093, 16381, 65521, 262139, 1048573, 4194301, 16777213, 67108859, 268435399, 1073741789, 4294967291, 17179869143, 68719476731, 274877906899, 1099511627689, 4398046511093, 17592186044399, 70368744177643

Offset: 1

Cino Hilliard, Mar 03 2005

Cf. A014234, A104082, A104088, A104090-A104094, A003618, A104096.

Cf. A000040, A000302, A007917.

NextPrime[4^Range[30], -1] (* Paolo Xausa, Oct 28 2024 *)

g(n,b) = for(x=0,n,print1(precprime(b^x)","))

a(n) = A007917(A000302(n)). - Paolo Xausa, Oct 28 2024

A185192 Number of primes less than 2^n.

Original entry on oeis.org

0, 2, 4, 6, 11, 18, 31, 54, 97, 172, 309, 564, 1028, 1900, 3512, 6542, 12251, 23000, 43390, 82025, 155611, 295947, 564163, 1077871, 2063689, 3957809, 7603553, 14630843, 28192750, 54400028, 105097565, 203280221, 393615806, 762939111, 1480206279, 2874398515

Offset: 1

Washington Bomfim, Jan 23 2012

This sequence differs from A007053 in the offset and in that the latter includes 1 (since the prime 2 is equal to 2^1, not less than it).

Number of primes with at most n bits.

			a(7) = 31 because prime(31) = 127, prime(32) = 131, and 127 < 2^7 < 131.

David Baugh, Table of n, a(n) for n = 1..90 (terms n = 1..81 from Charles R Greathouse IV).
Wikipedia, Prime-counting function.

Cf. A000720, A006880, A007053, A014234.

PrimePi[2^Range[32] - 1] (* Alonso del Arte, May 05 2019 *)

a(n)=primepi(2^n-1) \\ Charles R Greathouse IV, Dec 04 2014

a(n) = A000720(2^n - 1).

a(n) = A007053(n) for n > 1.

cp's OEIS Frontend

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

A377467 Number of perfect-powers x in the range 2^n < x < 2^(n+1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

A120274 Largest prime factor of the odd Catalan number A038003(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A102644 A006530(x)=2 is a local minimum if x=2^n. Running downward with argument x started at 2^n, the largest prime divisor should increase. The value of first peak is a(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A377702 Perfect-powers except for powers of 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

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