A049095 -id:A049095 - cp's OEIS frontend

A049094 Numbers m such that 2^m - 1 is divisible by a square > 1.

6, 12, 18, 20, 21, 24, 30, 36, 40, 42, 48, 54, 60, 63, 66, 72, 78, 80, 84, 90, 96, 100, 102, 105, 108, 110, 114, 120, 126, 132, 136, 138, 140, 144, 147, 150, 155, 156, 160, 162, 168, 174, 180, 186, 189, 192, 198, 200, 204, 210, 216, 220, 222, 228, 231, 234, 240

Offset: 1

Labos Elemer

nonn

Conjecture: 2^n-1 is squarefree iff gcd(n,2^n-1)=1. If true, the conjecture would imply that Mersenne numbers (A001348) are squarefree. - Vladeta Jovovic, Apr 12 2002. But the conjecture is not true: counterexamples are n = 364 and n = 1755, i.e., gcd(364,2^364-1) = 1 and (2^364-1) mod 1093^2 = 0 and gcd(1755,2^1755-1) = 1 and (2^1755-1) mod 3511^2 = 0, cf. A001220. - Vladeta Jovovic, Nov 01 2005. The conjecture is true with assumption that n is not a multiple of A002326((q-1)/2), where q is a Wieferich prime A001220. - Thomas Ordowski, Nov 17 2015
If d|n and 2^d-1 is not squarefree, then 2^n-1 cannot be squarefree. For example, if 6 is in the sequence then 6*d is also. - Enrique Pérez Herrero, Feb 28 2009
If p(p-1)|n then p^2|2^n-1, where p is an odd prime. - Thomas Ordowski, Jan 22 2014
The primitive elements of this sequence are A237043. - Charles R Greathouse IV, Feb 05 2014
Dilcher & Ericksen prove that this sequence is exactly the set of numbers divisible by either t(p)p for a Wieferich prime p>2 or t(p) for a non-Wieferich prime p, where t(p) is the order of 2 modulo p (see Proposition 3.1). - Kellen Myers, Jun 09 2015
If d^2 divides 2^n-1 then d divides n, where n is not a multiple of 364, 1755, ...; i.e., A002326((q-1)/2) for Wieferich primes q, A001220. - Thomas Ordowski, Nov 15 2015
(1, 2^n-1, 2^n) is an abc triple iff 2^n-1 is not squarefree. - William Hu, Jul 04 2024

			a(2)=12 because 2^12 - 1 = 4095 = 5*(3^2)*7*13 is divisible by a square.

R. K. Guy, Unsolved Problems in Number Theory, A3.

Max Alekseyev, Table of n, a(n) for n = 1..296
Karl Dilcher and Larry Ericksen, The Polynomials of Mahler and Roots of Unity, The American Mathematical Monthly, Vol. 122, No. 04 (April 2015), pp. 338-353.
Enrique Pérez Herrero, Mersenne Numbers Treasure Map, Psych Geom blogspot, 02/17/09
Andy Steward, Factorizations of Generalized Repunits [Dead link]

Cf. A001220, A001348, A002326, A014491, A049093, A049096, A049095, A237043, A282242, A282243.

[n: n in [1..250] | not IsSquarefree(2^n-1)]; // Vincenzo Librandi, Jul 14 2015

N:= 250:
B:= Vector(N):
for n from 1 to N do
  if B[n] <> 1 then
    F:= ifactors(2^n-1,easy)[2];
    if max(seq(t[2],t=F)) > 1 or (hastype(F,symbol)
            and not numtheory:-issqrfree(2^n-1)) then
       B[[seq(n*k,k=1..floor(N/n))]]:= 1;
    fi
  fi;
od:
select(t -> B[t]=1, [$1..N]); # Robert Israel, Nov 17 2015

Select[Range[240], !SquareFreeQ[2^#-1]&] (* Vladimir Joseph Stephan Orlovsky, Mar 18 2011 *)

default(factor_add_primes,1);
is(n)=my(f=factor(n>>valuation(n,2))[,1],N,o); for(i=1,#f,if(n%(f[i]-1) == 0, return(1))); N=2^n-1; fordiv(n,d,f=factor(2^d-1)[,1]; for(i=1,#f, if(d==n,return(!issquarefree(N))); o=valuation(N,f[i]); if(o>1, return(1)); N/=f[i]^o)) \\ Charles R Greathouse IV, Feb 02 2014

is(n)=!issquarefree(2^n-1) \\ Charles R Greathouse IV, Feb 04 2014

More terms from Vladeta Jovovic, Apr 12 2002

Definition corrected by Jonathan Sondow, Jun 29 2010

A104080 Smallest prime >= 2^n.

Original entry on oeis.org

2, 2, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459, 536870923, 1073741827, 2147483659

Offset: 0

Cino Hilliard, Mar 03 2005

Jinyuan Wang, Table of n, a(n) for n = 0..1000

Cf. A104081, A338475.
Except initial terms and offset, same as A014210 and A203074.
The opposite (greatest prime <= 2^n) is A014234, indices A007053.
The distance from 2^n is A092131, opposite A013603.
Counting zeros instead of both bits gives A372474, cf. A035103, A211997.
Counting ones instead of both bits gives A372517, cf. A014499, A061712.
For squarefree instead of prime we have A372683, cf. A143658, A372540.
The indices of these prime are given by A372684.
Cf. A007918, A007920, A029837, A035100, A049095, A130739.

Join[{2,2},NextPrime[#]&/@(2^Range[2,40])]  (* Harvey P. Dale, Jan 26 2011 *)
NextPrime[2^Range[0,50]-1]  (* Vladimir Joseph Stephan Orlovsky, Apr 11 2011 *)

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

a(n) = nextprime(2^n); \\ Michel Marcus, Nov 01 2020

a(n) = A014210(n), n <> 1. - R. J. Mathar, Oct 14 2008
Sum_{n >= 0} 1/a(n) = A338475 + 1/6 = 1.4070738... (because 1/6 = 1/2 - 1/3). - Bernard Schott, Nov 01 2020
From Gus Wiseman, Jun 03 2024: (Start)
a(n) = A007918(2^n).
a(n) = 2^n + A092131(n).
a(n) = prime(A372684(n)).
(End)

A372683 Least squarefree number >= 2^n.

Original entry on oeis.org

1, 2, 5, 10, 17, 33, 65, 129, 257, 514, 1027, 2049, 4097, 8193, 16385, 32770, 65537, 131073, 262145, 524289, 1048577, 2097154, 4194305, 8388609, 16777217, 33554433, 67108865, 134217730, 268435457, 536870913, 1073741826, 2147483649, 4294967297, 8589934594

Offset: 0

Gus Wiseman, May 26 2024

nonn

			The terms together with their binary expansions and binary indices begin:
       1:                    1 ~ {1}
       2:                   10 ~ {2}
       5:                  101 ~ {1,3}
      10:                 1010 ~ {2,4}
      17:                10001 ~ {1,5}
      33:               100001 ~ {1,6}
      65:              1000001 ~ {1,7}
     129:             10000001 ~ {1,8}
     257:            100000001 ~ {1,9}
     514:           1000000010 ~ {2,10}
    1027:          10000000011 ~ {1,2,11}
    2049:         100000000001 ~ {1,12}
    4097:        1000000000001 ~ {1,13}
    8193:       10000000000001 ~ {1,14}
   16385:      100000000000001 ~ {1,15}
   32770:     1000000000000010 ~ {2,16}
   65537:    10000000000000001 ~ {1,17}
  131073:   100000000000000001 ~ {1,18}
  262145:  1000000000000000001 ~ {1,19}
  524289: 10000000000000000001 ~ {1,20}

For primes instead of powers of two we have A112926, opposite A112925, sum A373197, length A373198.
Counting zeros instead of all bits gives A372473, firsts of A372472.
These are squarefree numbers at indices A372540, firsts of A372475.
Counting ones instead of all bits gives A372541, firsts of A372433.
The opposite (greatest squarefree number <= 2^n) is A372889.
The difference from 2^n is A373125.
For prime instead of squarefree we have:
- bits A372684, firsts of A035100
- zeros A372474, firsts of A035103
- ones A372517, firsts of A014499
A000120 counts ones in binary expansion (binary weight), zeros A080791.
A005117 lists squarefree numbers.
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.
A143658 counts squarefree numbers up to 2^n.
Cf. A029931, A048793, A049095, A049096, A059015, A069010, A076259, A077641, A211997, A230877.

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

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

from itertools import count
from sympy import factorint
def A372683(n): return next(i for i in count(1<Chai Wah Wu, Aug 26 2024

a(n) = A005117(A372540(n)).

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

A372684 Least k such that prime(k) >= 2^n.

Original entry on oeis.org

1, 3, 5, 7, 12, 19, 32, 55, 98, 173, 310, 565, 1029, 1901, 3513, 6543, 12252, 23001, 43391, 82026, 155612, 295948, 564164, 1077872, 2063690, 3957810, 7603554, 14630844, 28192751, 54400029, 105097566, 203280222, 393615807, 762939112, 1480206280, 2874398516, 5586502349

Offset: 1

Gus Wiseman, May 30 2024

nonn

			The numbers prime(a(n)) together with their binary expansions and binary indices begin:
        2:                       10 ~ {2}
        5:                      101 ~ {1,3}
       11:                     1011 ~ {1,2,4}
       17:                    10001 ~ {1,5}
       37:                   100101 ~ {1,3,6}
       67:                  1000011 ~ {1,2,7}
      131:                 10000011 ~ {1,2,8}
      257:                100000001 ~ {1,9}
      521:               1000001001 ~ {1,4,10}
     1031:              10000000111 ~ {1,2,3,11}
     2053:             100000000101 ~ {1,3,12}
     4099:            1000000000011 ~ {1,2,13}
     8209:           10000000010001 ~ {1,5,14}
    16411:          100000000011011 ~ {1,2,4,5,15}
    32771:         1000000000000011 ~ {1,2,16}
    65537:        10000000000000001 ~ {1,17}
   131101:       100000000000011101 ~ {1,3,4,5,18}
   262147:      1000000000000000011 ~ {1,2,19}
   524309:     10000000000000010101 ~ {1,3,5,20}
  1048583:    100000000000000000111 ~ {1,2,3,21}
  2097169:   1000000000000000010001 ~ {1,5,22}
  4194319:  10000000000000000001111 ~ {1,2,3,4,23}
  8388617: 100000000000000000001001 ~ {1,4,24}

The opposite (greatest k such that prime(k) <= 2^n) is A007053.
Positions of first appearances in A035100.
The distance from prime(a(n)) to 2^n is A092131.
Counting zeros instead of all bits gives A372474, firsts of A035103.
Counting ones instead of all bits gives A372517, firsts of A014499.
For primes between powers of 2:
- sum A293697
- length A036378
- min A104080 or A014210
- max A014234, delta A013603
For squarefree numbers between powers of 2:
- sum A373123
- length A077643, run-lengths of A372475
- min A372683, delta A373125, indices A372540
- max A372889, delta A373126, indices A143658
For squarefree numbers between primes:
- sum A373197
- length A373198 = A061398 - 1
- min A000040
- max A112925, opposite A112926
Cf. A000120, A029837, A029931, A030190, A049095, A069010, A070939, A077641, A080791, A211997.

Table[PrimePi[If[n==1,2,NextPrime[2^n]]],{n,30}]

a(n) = primepi(nextprime(2^n)); \\ Michel Marcus, May 31 2024

a(n>1) = A007053(n) + 1.
a(n) = A000720(A104080(n)).
prime(a(n)) = A104080(n).
prime(a(n)) - 2^n = A092131(n).

More terms from Michel Marcus, May 31 2024

A049096 Numbers k such that 2^k + 1 is divisible by a square > 1.

Original entry on oeis.org

3, 9, 10, 15, 21, 27, 30, 33, 39, 45, 50, 51, 55, 57, 63, 68, 69, 70, 75, 78, 81, 87, 90, 93, 99, 105, 110, 111, 117, 123, 129, 130, 135, 141, 147, 150, 153, 159, 165, 170, 171, 177, 182, 183, 189, 190, 195, 201, 204, 207, 210, 213, 219, 225, 230, 231, 234, 237, 243

Offset: 1

Labos Elemer

nonn

Conjecture: lim n -> infinity a(n)/n = C exists and 4 < C < 9/2. There seems to be a sequence of primes p such that p^2 never divides numbers of the form 2^x + 1: the first few are 2, 7, 23, 31. - Benoit Cloitre, Aug 20 2002
That sequence is A072936. - Robert Israel, Nov 20 2015
The first case where 2^n + 1 is divisible by a square that is coprime to n is n = 182 (where 2^182 + 1 is divisible by 1093^2). - Robert Israel, Jul 07 2014
From Robert Israel, Nov 20 2015: (Start)
Numbers n such that gcd(n, 2^n + 1) > 1 or n = k m where k is odd and 2 m is the order of 2 modulo a Wieferich prime.  See link "When p^2 divides 2^n + 1".
If n is in the sequence, then so is k*n for any odd k. (End)
The sequence consists of all odd multiples of { 3, 10, 55, 68, 78, 182, 301, 406, 666, ... }. - M. F. Hasler, Mar 06 2018

			9 is here because 2^9 + 1 = 513 is divisible by 9.
99 is here because 2^99 + 1 = 3^3*19*67*683*5347*20857*242099935645987 is divisible by 9, i.e. is not squarefree.

Robert Israel, Table of n, a(n) for n = 1..10000
Robert Israel, When p^2 divides 2^n + 1

Cf. A001220, A049093, A049094, A049095, A072936, A282269, A282270.

Cf. A086982, which is just the same with base b = 10 instead of b = 2.

[n: n in [3..220] | not IsSquarefree(2^n+1)]; // Vincenzo Librandi, Mar 08 2018

remove(n -> numtheory:-issqrfree(2^n+1), [$1..250]); # Robert Israel, Jul 07 2014

Select[Range[243], !SquareFreeQ[2^# + 1] &] (* Vladimir Joseph Stephan Orlovsky, Mar 18 2011*)

is(n)=!issquarefree(2^n+1) \\ Altug Alkan, Nov 20 2015

For any a(n+1) - a(n) <= 6 since numbers of form 3^a*(2k+1) a > 0, k >= 0, are in the sequence (2^(3*(2k+1) + 1 is divisible by 9). So are numbers of the form 20k + 10 since 2^(20k+10) + 1 is divisible by 25, 110k + 55 since 2^(110k+55) + 1 is divisible by 11^2, 78 + 156k since 2^(156k+78) + 1 is divisible by 13^2 ... - Benoit Cloitre, Aug 20 2002

More terms from James Sellers, Dec 16 1999
More terms from Vladeta Jovovic, Apr 12 2002
Missing term 182 added by Rainer Rosenthal, Nov 01 2005

A373413 Sum of the n-th maximal run of squarefree numbers.

Original entry on oeis.org

6, 18, 21, 42, 17, 19, 66, 26, 90, 102, 114, 126, 93, 51, 53, 55, 174, 123, 198, 210, 147, 234, 165, 258, 89, 91, 282, 97, 306, 318, 330, 342, 237, 245, 127, 390, 267, 414, 426, 291, 149, 151, 309, 474, 161, 163, 498, 170, 347, 534, 546, 558, 381, 582, 197

Offset: 1

Gus Wiseman, Jun 05 2024

nonn

The length of this run is given by A120992.

A run of a sequence (in this case A005117) is an interval of positions at which consecutive terms differ by one.

			Row-sums of:
   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

Gus Wiseman, Four statistics for runs and antiruns of prime, nonprime, squarefree, and nonsquarefree numbers

The partial sums are a subset of A173143.
Functional neighbors: A054265, A072284, A120992, A373406, A373411, A373414, A373415.
A005117 lists the squarefree numbers, first differences A076259.
A013929 lists the nonsquarefree numbers, first differences A078147.
Cf. A049093, A049095, A061398, A077641, A077643, A143658, A371201, A373123, A373125, A373126, A373197.

Total/@Split[Select[Range[100],SquareFreeQ],#1+1==#2&]//Most

A069226 a(n) = gcd(n, 2^n + 1).

Original entry on oeis.org

2, 1, 1, 3, 1, 1, 1, 1, 1, 9, 5, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 27, 1, 1, 5, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 9, 1, 1, 1, 1, 25, 3, 1, 1, 1, 11, 1, 3, 1, 1, 1, 1, 1, 9, 1, 1, 1, 1, 17, 3, 5, 1, 1, 1, 1, 3, 1, 1, 13, 1, 1, 81, 1, 1, 1, 1, 1, 3, 1, 1, 5, 1, 1, 3, 1, 1, 1, 1, 1, 9, 1

Offset: 0

Vladeta Jovovic, Apr 12 2002

nonn

First occurrence of n: a(1)=1, a(3)=3, a(10)=5, a(9)=9, a(55)=11, a(78)=13, a(68)=17, a(50)=25, a(27)=27, a(406)=29, a(165)=33, a(666)=37, a(301)=43, a(1378)=53, a(1711)=59, a(390)=65, a(81)=81, a(3403)=83, a(2328)=97, a(495)=99, ... - R. J. Mathar, Dec 14 2016

Antti Karttunen, Table of n, a(n) for n = 0..65537

Cf. A006521 (fixed points), A014491, A049095, A049096, A060444.

Table[GCD[n,2^n+1],{n,100}] (* Harvey P. Dale, Dec 12 2012 *)

A069226(n) = gcd(n, 1+(1<Antti Karttunen, Jan 15 2025

Term a(0) = 2 prepended by Antti Karttunen, Jan 15 2025

A172522 Partial sums of A049094.

Original entry on oeis.org

6, 18, 36, 56, 77, 101, 131, 167, 207, 249, 297, 351, 411, 474, 540, 612, 690, 770, 854, 944, 1040, 1140, 1242, 1347, 1455, 1565, 1679, 1799, 1925, 2057, 2193, 2331, 2471, 2615, 2762, 2912, 3067, 3223, 3383, 3545, 3713, 3887, 4067, 4253, 4442, 4634, 4832

Offset: 1

Jonathan Vos Post, Feb 06 2010

nonn

The subsequence of primes in this sequence begins: 101, 131, 167, 3067.

			a(20) = 6 + 12 + 18 + 20 + 21 + 24 + 30 + 36 + 40 + 42 + 48 + 54 + 60 + 63 + 66 + 72 + 78 + 80 + 84 + 90.

Cf. A000040, A014491, A049093, A049096, A049095, A001220.

a(n) = SUM[i=1..n] {i such that 2^i - 1 is divisible by a square}.

More terms from R. J. Mathar, Feb 16 2010

cp's OEIS Frontend

A049094 Numbers m such that 2^m - 1 is divisible by a square > 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Extensions

A104080 Smallest prime >= 2^n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A372683 Least squarefree number >= 2^n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A372684 Least k such that prime(k) >= 2^n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A049096 Numbers k such that 2^k + 1 is divisible by a square > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A373413 Sum of the n-th maximal run of squarefree numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A069226 a(n) = gcd(n, 2^n + 1).

Views

Author

Keywords

Comments