cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 21-30 of 245 results. Next

A001220 Wieferich primes: primes p such that p^2 divides 2^(p-1) - 1.

Original entry on oeis.org

1093, 3511
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Sequence is believed to be infinite.
Joseph Silverman showed that the abc-conjecture implies that there are infinitely many primes which are not in the sequence. - Benoit Cloitre, Jan 09 2003
Graves and Murty (2013) improved Silverman's result by showing that for any fixed k > 1, the abc-conjecture implies that there are infinitely many primes == 1 (mod k) which are not in the sequence. - Jonathan Sondow, Jan 21 2013
The squares of these numbers are Fermat pseudoprimes to base 2 (A001567) and Catalan pseudoprimes (A163209). - T. D. Noe, May 22 2003
Primes p that divide the numerator of the harmonic number H((p-1)/2); that is, p divides A001008((p-1)/2). - T. D. Noe, Mar 31 2004
In a 1977 paper, Wells Johnson, citing a suggestion from Lawrence Washington, pointed out the repetitions in the binary representations of the numbers which are one less than the two known Wieferich primes; i.e., 1092 = 10001000100 (base 2); 3510 = 110110110110 (base 2). It is perhaps worth remarking that 1092 = 444 (base 16) and 3510 = 6666 (base 8), so that these numbers are small multiples of repunits in the respective bases. Whether this is mathematically significant does not appear to be known. - John Blythe Dobson, Sep 29 2007
A002326((a(n)^2 - 1)/2) = A002326((a(n)-1)/2). - Vladimir Shevelev, Jul 09 2008, Aug 24 2008
It is believed that p^2 does not divide 3^(p-1) - 1 if p = a(n). This is true for n = 1 and 2. See A178815, A178844, A178900, and Ostafe-Shparlinski (2010) Section 1.1. - Jonathan Sondow, Jun 29 2010
These primes also divide the numerator of the harmonic number H(floor((p-1)/4)). - H. Eskandari (hamid.r.eskandari(AT)gmail.com), Sep 28 2010
1093 and 3511 are prime numbers p satisfying congruence 429327^(p-1) == 1 (mod p^2). Why? - Arkadiusz Wesolowski, Apr 07 2011. Such bases are listed in A247208. - Max Alekseyev, Nov 25 2014. See A269798 for all such bases, prime and composite, that are not powers of 2. - Felix Fröhlich, Apr 07 2018
A196202(A049084(a(1))) = A196202(A049084(a(2))) = 1. - Reinhard Zumkeller, Sep 29 2011
If q is prime and q^2 divides a prime-exponent Mersenne number, then q must be a Wieferich prime. Neither of the two known Wieferich primes divide Mersenne numbers. See Will Edgington's Mersenne page in the links below. - Daran Gill, Apr 04 2013
There are no other terms below 4.97*10^17 as established by PrimeGrid (see link below). - Max Alekseyev, Nov 20 2015. The search was done via PrimeGrid's PRPNet and the results were not double-checked. Because of the unreliability of the testing, the search was suspended in May 2017 (cf. Goetz, 2017). - Felix Fröhlich, Apr 01 2018. On Nov 28 2020, PrimeGrid has resumed the search (cf. Reggie, 2020). - Felix Fröhlich, Nov 29 2020. As of Dec 29 2022, PrimeGrid has completed the search to 2^64 (about 1.8 * 10^19) and has no plans to continue further. - Charles R Greathouse IV, Sep 24 2024
Are there other primes q >= p such that q^2 divides 2^(p-1)-1, where p is a prime? - Thomas Ordowski, Nov 22 2014. Any such q must be a Wieferich prime. - Max Alekseyev, Nov 25 2014
Primes p such that p^2 divides 2^r - 1 for some r, 0 < r < p. - Thomas Ordowski, Nov 28 2014, corrected by Max Alekseyev, Nov 28 2014
For some reason, both p=a(1) and p=a(2) also have more bases b with 1 < b < p that make b^(p-1) == 1 (mod p^2) than any smaller prime p; in other words, a(1) and a(2) belong to A248865. - Jeppe Stig Nielsen, Jul 28 2015
Let r_1, r_2, r_3, ..., r_i be the set of roots of the polynomial X^((p-1)/2) - (p-3)! * X^((p-3)/2) - (p-5)! * X^((p-5)/2) - ... - 1. Then p is a Wieferich prime iff p divides sum{k=1, p}(r_k^((p-1)/2)) (see Example 2 in Jakubec, 1994). - Felix Fröhlich, May 27 2016
Arthur Wieferich showed that if p is not a term of this sequence, then the First Case of Fermat's Last Theorem has no solution in x, y and z for prime exponent p (cf. Wieferich, 1909). - Felix Fröhlich, May 27 2016
Let U_n(P, Q) be a Lucas sequence of the first kind, let e be the Legendre symbol (D/p) and let p be a prime not dividing 2QD, where D = P^2 - 4*Q. Then a prime p such that U_(p-e) == 0 (mod p^2) is called a "Lucas-Wieferich prime associated to the pair (P, Q)". Wieferich primes are those Lucas-Wieferich primes that are associated to the pair (3, 2) (cf. McIntosh, Roettger, 2007, p. 2088). - Felix Fröhlich, May 27 2016
Any repeated prime factor of a term of A000215 is a term of this sequence. Thus, if there exist infinitely many Fermat numbers that are not squarefree, then this sequence is infinite, since no two Fermat numbers share a common factor. - Felix Fröhlich, May 27 2016
If the Diophantine equation p^x - 2^y = d has more than one solution in positive integers (x, y), with (p, d) not being one of the pairs (3, 1), (3, -5), (3, -13) or (5, -3), then p is a term of this sequence (cf. Scott, Styer, 2004, Corollary to Theorem 2). - Felix Fröhlich, Jun 18 2016
Odd primes p such that Chi_(D_0)(p) != 1 and Lambda_p(Q(sqrt(D_0))) != 1, where D_0 < 0 is the fundamental discriminant of the imaginary quadratic field Q(sqrt(1-p^2)) and Chi and Lambda are Iwasawa invariants (cf. Byeon, 2006, Proposition 1 (i)). - Felix Fröhlich, Jun 25 2016
If q is an odd prime, k, p are primes with p = 2*k+1, k == 3 (mod 4), p == -1 (mod q) and p =/= -1 (mod q^3) (Jakubec, 1998, Corollary 2 gives p == -5 (mod q) and p =/= -5 (mod q^3)) with the multiplicative order of q modulo k = (k-1)/2 and q dividing the class number of the real cyclotomic field Q(Zeta_p + (Zeta_p)^(-1)), then q is a term of this sequence (cf. Jakubec, 1995, Theorem 1). - Felix Fröhlich, Jun 25 2016
From Felix Fröhlich, Aug 06 2016: (Start)
Primes p such that p-1 is in A240719.
Prime terms of A077816 (cf. Agoh, Dilcher, Skula, 1997, Corollary 5.9).
p = prime(n) is in the sequence iff T(2, n) > 1, where T = A258045.
p = prime(n) is in the sequence iff an integer k exists such that T(n, k) = 2, where T = A258787. (End)
Conjecture: an integer n > 1 such that n^2 divides 2^(n-1)-1 must be a Wieferich prime. - Thomas Ordowski, Dec 21 2016
The above conjecture is equivalent to the statement that no "Wieferich pseudoprimes" (WPSPs) exist. While base-b WPSPs are known to exist for several bases b > 1 other than 2 (see for example A244752), no base-2 WPSPs are known. Since two necessary conditions for a composite to be a base-2 WPSP are that, both, it is a base-2 Fermat pseudoprime (A001567) and all its prime factors are Wieferich primes (cf. A270833), as shown in the comments in A240719, it seems that the first base-2 WPSP, if it exists, is probably very large. This appears to be supported by the guess that the properties of a composite to be a term of A001567 and of A270833 are "independent" of each other and by the observation that the scatterplot of A256517 seems to become "less dense" at the x-axis parallel line y = 2 for increasing n. It has been suggested in the literature that there could be asymptotically about log(log(x)) Wieferich primes below some number x, which is a function that grows to infinity, but does so very slowly. Considering the above constraints, the number of WPSPs may grow even more slowly, suggesting any such number, should it exist, probably lies far beyond any bound a brute-force search could reach in the forseeable future. Therefore I guess that the conjecture may be false, but a disproof or the discovery of a counterexample are probably extraordinarily difficult problems. - Felix Fröhlich, Jan 18 2019
Named after the German mathematician Arthur Josef Alwin Wieferich (1884-1954). a(1) = 1093 was found by Waldemar Meissner in 1913. a(2) = 3511 was found by N. G. W. H. Beeger in 1922. - Amiram Eldar, Jun 05 2021
From Jianing Song, Jun 21 2025: (Start)
The ring of integers of Q(2^(1/k)) is Z[2^(1/k)] if and only if k does not have a prime factor in this sequence (k is in A342390). See Theorem 5.3 of the paper of Keith Conrad. For example, we have:
(1 + 2^(364/1093) + 2^(2*364/1093) + ... + 2^(1092*364/1093))/1093 is an algebraic integer, but it is not in Z[2^(1/1093)];
(1 + 2^(1755/3511) + 2^(2*1755/3511) + ... + 2^(3510*1755/3511))/3511 is an algebraic integer, but it is not in Z[2^(1/3511)]. (End)

References

  • Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 28.
  • Richard K. Guy, Unsolved Problems in Number Theory, A3.
  • G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 91.
  • Yves Hellegouarch, "Invitation aux mathématiques de Fermat Wiles", Dunod, 2eme Edition, pp. 340-341.
  • Pace Nielsen, Wieferich primes, heuristics, computations, Abstracts Amer. Math. Soc., 33 (#1, 20912), #1077-11-48.
  • Paulo Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 263.
  • Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 230-234.
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, NY, 1986, p. 163.

Links

Crossrefs

Cf. similar primes related to the first case of Fermat's last theorem: A007540, A088164.
Sequences "primes p such that p^2 divides X^(p-1)-1": A014127 (X=3), A123692 (X=5), A212583 (X=6), A123693 (X=7), A045616 (X=10), A111027 (X=12), A128667 (X=13), A234810 (X=14), A242741 (X=15), A128668 (X=17), A244260 (X=18), A090968 (X=19), A242982 (X=20), A298951 (X=22), A128669 (X=23), A306255 (X=26), A306256 (X=30).
Cf. A001567, A002323, A077816, A001008, A039951, A049094, A126196, A126197, A178815, A178844, A178871, A178900, A246503, A247208, A269798.

Programs

  • GAP
    Filtered([1..50000],p->IsPrime(p) and (2^(p-1)-1) mod p^2 =0); # Muniru A Asiru, Apr 03 2018
  • Haskell
    import Data.List (elemIndices)
a001220 n = a001220_list !! (n-1)
a001220_list = map (a000040 . (+ 1)) $ elemIndices 1 a196202_list
-- Reinhard Zumkeller, Sep 29 2011
  • Magma
    [p : p in PrimesUpTo(310000) | IsZero((2^(p-1) - 1) mod (p^2))]; // Vincenzo Librandi, Jan 19 2019
  • Maple
    wieferich := proc (n) local nsq, remain, bin, char: if (not isprime(n)) then RETURN("not prime") fi: nsq := n^2: remain := 2: bin := convert(convert(n-1, binary),string): remain := (remain * 2) mod nsq: bin := substring(bin,2..length(bin)): while (length(bin) > 1) do: char := substring(bin,1..1): if char = "1" then remain := (remain * 2) mod nsq fi: remain := (remain^2) mod nsq: bin := substring(bin,2..length(bin)): od: if (bin = "1") then remain := (remain * 2) mod nsq fi: if remain = 1 then RETURN ("Wieferich prime") fi: RETURN ("non-Wieferich prime"): end: # Ulrich Schimke (ulrschimke(AT)aol.com), Nov 01 2001
  • Mathematica
    Select[Prime[Range[50000]],Divisible[2^(#-1)-1,#^2]&]  (* Harvey P. Dale, Apr 23 2011 *)
Select[Prime[Range[50000]],PowerMod[2,#-1,#^2]==1&] (* Harvey P. Dale, May 25 2016 *)
  • PARI
    N=10^4; default(primelimit,N);
forprime(n=2,N,if(Mod(2,n^2)^(n-1)==1,print1(n,", ")));
\\ Joerg Arndt, May 01 2013
  • Python
    from sympy import prime
from gmpy2 import powmod
A001220_list = [p for p in (prime(n) for n in range(1,10**7)) if powmod(2,p-1,p*p) == 1]
# Chai Wah Wu, Dec 03 2014

Formula

(A178815(A000720(p))^(p-1) - 1) mod p^2 = A178900(n), where p = a(n). - Jonathan Sondow, Jun 29 2010
Odd primes p such that A002326((p^2-1)/2) = A002326((p-1)/2). See A182297. - Thomas Ordowski, Feb 04 2014

A000058 Sylvester's sequence: a(n+1) = a(n)^2 - a(n) + 1, with a(0) = 2.

Original entry on oeis.org

2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443, 12864938683278671740537145998360961546653259485195807
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Also called Euclid numbers, because a(n) = a(0)*a(1)*...*a(n-1) + 1 for n>0, with a(0)=2. - Jonathan Sondow, Jan 26 2014
Another version of this sequence is given by A129871, which starts with 1, 2, 3, 7, 43, 1807, ... .
The greedy Egyptian representation of 1 is 1 = 1/2 + 1/3 + 1/7 + 1/43 + 1/1807 + ... .
Take a square. Divide it into 2 equal rectangles by drawing a horizontal line. Divide the upper rectangle into 2 squares. Now you can divide the lower one into another 2 squares, but instead of doing so draw a horizontal line below the first one so you obtain a (2+1 = 3) X 1 rectangle which can be divided in 3 squares. Now you have a 6 X 1 rectangle at the bottom. Instead of dividing it into 6 squares, draw another horizontal line so you obtain a (6+1 = 7) X 1 rectangle and a 42 X 1 rectangle left, etc. - Néstor Romeral Andrés, Oct 29 2001
More generally one may define f(1) = x_1, f(2) = x_2, ..., f(k) = x_k, f(n) = f(1)*...*f(n-1)+1 for n > k and natural numbers x_i (i = 1, ..., k) which satisfy gcd(x_i, x_j) = 1 for i <> j. By definition of the sequence we have that for each pair of numbers x, y from the sequence gcd(x, y) = 1. An interesting property of a(n) is that for n >= 2, 1/a(0) + 1/a(1) + 1/a(2) + ... + 1/a(n-1) = (a(n)-2)/(a(n)-1). Thus we can also write a(n) = (1/a(0) + 1/a(1) + 1/a(2) + ... + 1/a(n-1) - 2 )/( 1/a(0) + 1/a(1) + 1/a(2) + ... + 1/a(n-1) - 1). - Frederick Magata (frederick.magata(AT)uni-muenster.de), May 10 2001; [corrected by Michel Marcus, Mar 27 2019]
A greedy sequence: a(n+1) is the smallest integer > a(n) such that 1/a(0) + 1/a(1) + 1/a(2) + ... + 1/a(n+1) doesn't exceed 1. The sequence gives infinitely many ways of writing 1 as the sum of Egyptian fractions: Cut the sequence anywhere and decrement the last element. 1 = 1/2 + 1/3 + 1/6 = 1/2 + 1/3 + 1/7 + 1/42 = 1/2 + 1/3 + 1/7 + 1/43 + 1/1806 = ... . - Ulrich Schimke, Nov 17 2002; [corrected by Michel Marcus, Mar 27 2019]
Consider the mapping f(a/b) = (a^3 + b)/(a + b^3). Starting with a = 1, b = 2 and carrying out this mapping repeatedly on each new (reduced) rational number gives 1/2, 1/3, 4/28 = 1/7, 8/344 = 1/43, ..., i.e., 1/2, 1/3, 1/7, 1/43, 1/1807, ... . Sequence contains the denominators. Also the sum of the series converges to 1. - Amarnath Murthy, Mar 22 2003
a(1) = 2, then the smallest number == 1 (mod all previous terms). a(2n+6) == 443 (mod 1000) and a(2n+7) == 807 (mod 1000). - Amarnath Murthy, Sep 24 2003
An infinite coprime sequence defined by recursion.
Apart from the initial 2, a subsequence of A002061. It follows that no term is a square.
It appears that a(k)^2 + 1 divides a(k+1)^2 + 1. - David W. Wilson, May 30 2004. This is true since a(k+1)^2 + 1 = (a(k)^2 - a(k) + 1)^2 +1 = (a(k)^2-2*a(k)+2)*(a(k)^2 + 1) (a(k+1)=a(k)^2-a(k)+1 by definition). - Pab Ter (pabrlos(AT)yahoo.com), May 31 2004
In general, for any m > 0 coprime to a(0), the sequence a(n+1) = a(n)^2 - m*a(n) + m is infinite coprime (Mohanty). This sequence has (m,a(0))=(1,2); (2,3) is A000215; (1,4) is A082732; (3,4) is A000289; (4,5) is A000324.
Any prime factor of a(n) has -3 as its quadratic residue (Granville, exercise 1.2.3c in Pollack).
Note that values need not be prime, the first composites being 1807 = 13 * 139 and 10650056950807 = 547 * 19569939581. - Jonathan Vos Post, Aug 03 2008
If one takes any subset of the sequence comprising the reciprocals of the first n terms, with the condition that the first term is negated, then this subset has the property that the sum of its elements equals the product of its elements. Thus -1/2 = -1/2, -1/2 + 1/3 = -1/2 * 1/3, -1/2 + 1/3 + 1/7 = -1/2 * 1/3 * 1/7, -1/2 + 1/3 + 1/7 + 1/43 = -1/2 * 1/3 * 1/7 * 1/43, and so on. - Nick McClendon, May 14 2009
(a(n) + a(n+1)) divides a(n)*a(n+1)-1 because a(n)*a(n+1) - 1 = a(n)*(a(n)^2 - a(n) + 1) - 1 = a(n)^3 - a(n)^2 + a(n) - 1 = (a(n)^2 + 1)*(a(n) - 1) = (a(n) + a(n)^2 - a(n) + 1)*(a(n) - 1) = (a(n) + a(n+1))*(a(n) - 1). - Mohamed Bouhamida, Aug 29 2009
This sequence is also related to the short side (or hypotenuse) of adjacent right triangles, (3, 4, 5), (5, 12, 13), (13, 84, 85), ... by A053630(n) = 2*a(n) - 1. - Yuksel Yildirim, Jan 01 2013, edited by M. F. Hasler, May 19 2017
For n >= 4, a(n) mod 3000 alternates between 1807 and 2443. - Robert Israel, Jan 18 2015
The set of prime factors of a(n)'s is thin in the set of primes. Indeed, Odoni showed that the number of primes below x dividing some a(n) is O(x/(log x log log log x)). - Tomohiro Yamada, Jun 25 2018
Sylvester numbers when reduced modulo 864 form the 24-term arithmetic progression 7, 43, 79, 115, 151, 187, 223, 259, 295, 331, ..., 763, 799, 835 which repeats itself until infinity. This was first noticed in March 2018 and follows from the work of Sondow and MacMillan (2017) regarding primary pseudoperfect numbers which similarly form an arithmetic progression when reduced modulo 288. Giuga numbers also form a sequence resembling an arithmetic progression when reduced modulo 288. - Mehran Derakhshandeh, Apr 26 2019
Named after the English mathematician James Joseph Sylvester (1814-1897). - Amiram Eldar, Mar 09 2024
Guy askes if it is an irrationality sequence (see Guy, 1981). - Stefano Spezia, Oct 13 2024

Examples

			a(0)=2, a(1) = 2+1 = 3, a(2) = 2*3 + 1 = 7, a(3) = 2*3*7 + 1 = 43.

References

  • Graham Everest, Alf van der Poorten, Igor Shparlinski and Thomas Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
  • Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 6.7.
  • Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994.
  • Richard K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section E24.
  • Richard K. Guy and Richard Nowakowski, Discovering primes with Euclid. Delta, Vol. 5 (1975), pp. 49-63.
  • Amarnath Murthy, Smarandache Reciprocal partition of unity sets and sequences, Smarandache Notions Journal, Vol. 11, 1-2-3, Spring 2000.
  • Amarnath Murthy and Charles Ashbacher, Generalized Partitions and Some New Ideas on Number Theory and Smarandache Sequences, Hexis, Phoenix; USA 2005. See Section 1.1.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A005267, A000945, A000946, A005265, A005266, A075442, A007018, A014117, A054377, A002061, A118227, A126263, A007996 (primes dividing some term), A323605 (smallest prime divisors), A091335 (number of prime divisors), A129871 (a variant starting with 1).

Programs

  • Haskell
    a000058 0 = 2
a000058 n = a000058 m ^ 2 - a000058 m + 1 where m = n - 1
-- James Spahlinger, Oct 09 2012
  • Haskell
    a000058_list = iterate a002061 2  -- Reinhard Zumkeller, Dec 18 2013
  • Julia
    a(n) = n == 0 ? BigInt(2) : a(n - 1)*(a(n - 1) - 1) + 1
[a(n) for n in 0:8] |> println # Peter Luschny, Dec 15 2020
  • Maple
    A[0]:= 2:
for n from 1 to 12 do
A[n]:= A[n-1]^2 - A[n-1]+1
od:
seq(A[i],i=0..12); # Robert Israel, Jan 18 2015
  • Mathematica
    a[0] = 2; a[n_] := a[n - 1]^2 - a[n - 1] + 1; Table[ a[ n ], {n, 0, 9} ]
NestList[#^2-#+1&,2,10] (* Harvey P. Dale, May 05 2013 *)
RecurrenceTable[{a[n + 1] == a[n]^2 - a[n] + 1, a[0] == 2}, a, {n, 0, 10}] (* Emanuele Munarini, Mar 30 2017 *)
  • Maxima
    a(n) := if n = 0 then 2 else a(n-1)^2-a(n-1)+1 $
makelist(a(n),n,0,8); /* Emanuele Munarini, Mar 23 2017 */
  • PARI
    a(n)=if(n<1,2*(n>=0),1+a(n-1)*(a(n-1)-1))
  • PARI
    A000058(n,p=2)={for(k=1,n,p=(p-1)*p+1);p} \\ give Mod(2,m) as 2nd arg to calculate a(n) mod m. - M. F. Hasler, Apr 25 2014
  • PARI
    a=vector(20); a[1]=3; for(n=2, #a, a[n]=a[n-1]^2-a[n-1]+1); concat(2, a) \\ Altug Alkan, Apr 04 2018
  • Python
    A000058 = [2]
for n in range(1, 10):
    A000058.append(A000058[n-1]*(A000058[n-1]-1)+1)
# Chai Wah Wu, Aug 20 2014

Formula

a(n) = 1 + a(0)*a(1)*...*a(n-1).
a(n) = a(n-1)*(a(n-1)-1) + 1; Sum_{i>=0} 1/a(i) = 1. - Néstor Romeral Andrés, Oct 29 2001
Vardi showed that a(n) = floor(c^(2^(n+1)) + 1/2) where c = A076393 = 1.2640847353053011130795995... - Benoit Cloitre, Nov 06 2002 (But see the Aho-Sloane paper!)
a(n) = A007018(n+1)+1 = A007018(n+1)/A007018(n) [A007018 is a(n) = a(n-1)^2 + a(n-1), a(0)=1]. - Gerald McGarvey, Oct 11 2004
a(n) = sqrt(A174864(n+1)/A174864(n)). - Giovanni Teofilatto, Apr 02 2010
a(n) = A014117(n+1)+1 for n = 0,1,2,3,4; a(n) = A054377(n)+1 for n = 1,2,3,4. - Jonathan Sondow, Dec 07 2013
a(n) = f(1/(1-(1/a(0) + 1/a(1) + ... + 1/a(n-1)))) where f(x) is the smallest integer > x (see greedy algorithm above). - Robert FERREOL, Feb 22 2019
From Amiram Eldar, Oct 29 2020: (Start)
Sum_{n>=0} (-1)^n/(a(n)-1) = A118227.
Sum_{n>=0} (-1)^n/a(n) = 2 * A118227 - 1. (End)

A001146 a(n) = 2^(2^n).

Original entry on oeis.org

2, 4, 16, 256, 65536, 4294967296, 18446744073709551616, 340282366920938463463374607431768211456, 115792089237316195423570985008687907853269984665640564039457584007913129639936
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Or, write previous term in base 2, read in base 4.
a(1) = 2, a(n) = smallest power of 2 which does not divide the product of all previous terms.
Number of truth tables generated by Boolean expressions of n variables. - C. Bradford Barber (bradb(AT)shore.net), Dec 27 2005
From Ross Drewe, Feb 13 2008: (Start)
Or, number of distinct n-ary operators in a binary logic. The total number of n-ary operators in a k-valued logic is T = k^(k^n), i.e., if S is a set of k elements, there are T ways of mapping an ordered subset of n elements from S to an element of S. Some operators are "degenerate": the operator has arity p, if only p of the n input values influence the output. Therefore the set of operators can be partitioned into n+1 disjoint subsets representing arities from 0 to n.
For n = 2, k = 2 gives the familiar Boolean operators or functions, C = F(A,B). There are 2^2^2 = 16 operators, composed of: arity 0: 2 operators (C = 0 or 1), arity 1: 4 operators (C = A, B, not(A), not(B)), arity 2: 10 operators (including well-known pairs AND/NAND, OR/NOR, XOR/EQ). (End)
From José María Grau Ribas, Jan 19 2012: (Start)
Or, numbers that can be formed using the number 2, the power operator (^), and parenthesis. (End) [The paper by Guy and Selfridge (see also A003018) shows that this is the same as the current sequence. - N. J. A. Sloane, Jan 21 2012]
a(n) is the highest value k such that A173419(k) = n+1. - Charles R Greathouse IV, Oct 03 2012
Let b(0) = 8 and b(n+1) = the smallest number not in the sequence such that b(n+1) - Product_{i=0..n} b(i) divides b(n+1)*Product_{i=0..n} b(i). Then b(n) = a(n) for n > 0. - Derek Orr, Jan 15 2015
Twice the number of distinct minimal toss sequences of a coin to obtain all sequences of length n, which is 2^(2^n-1). This derives from the 2^n ways to cut each of the de Bruijn sequences B(2,n). - Maurizio De Leo, Feb 28 2015
I conjecture that { a(n) ; n>1 } are the numbers such that n^4-1 divides 2^n-1, intersection of A247219 and A247165. - M. F. Hasler, Jul 25 2015
Erdős has shown that it is an irrationality sequence (see Guy reference). - Stefano Spezia, Oct 13 2024

References

  • R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section E24.
  • D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A000079, A000215, A007404, A026477, A062090, A062091, A112535, A155538, A215016.
Cf. also A003018, A051179, A173419, A165420, A247165, A247219.

Programs

Formula

a(n+1) = (a(n))^2.
1 = Sum_{n>=0} a(n)/A051179(n+1) = 2/3 + 4/15 + 16/255 + 256/65535, ..., with partial sums: 2/3, 14/15, 254/255, 65534/65535, ... - Gary W. Adamson, Jun 15 2003
a(n) = A000079(A000079(n)). - Robert Israel, Jan 15 2015
Sum_{n>=0} 1/a(n) = A007404. - Amiram Eldar, Oct 14 2020
From Amiram Eldar, Jan 28 2021: (Start)
Product_{n>=0} (1 + 1/a(n)) = 2.
Product_{n>=0} (1 - 1/a(n)) = A215016. (End)

A001317 Sierpiński's triangle (Pascal's triangle mod 2) converted to decimal.

Original entry on oeis.org

1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 65535, 65537, 196611, 327685, 983055, 1114129, 3342387, 5570645, 16711935, 16843009, 50529027, 84215045, 252645135, 286331153, 858993459, 1431655765, 4294967295, 4294967297, 12884901891, 21474836485, 64424509455, 73014444049, 219043332147, 365072220245, 1095216660735, 1103806595329, 3311419785987
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

The members are all palindromic in binary, i.e., a subset of A006995. - Ralf Stephan, Sep 28 2004
J. H. Conway writes (in Math Forum): at least the first 31 numbers give odd-sided constructible polygons. See also A047999. - M. Dauchez (mdzzdm(AT)yahoo.fr), Sep 19 2005 [This observation was also made in 1982 by N. L. White (see letter). - N. J. A. Sloane, Jun 15 2015]
Decimal number generated by the binary bits of the n-th generation of the Rule 60 elementary cellular automaton. Thus: 1; 0, 1, 1; 0, 0, 1, 0, 1; 0, 0, 0, 1, 1, 1, 1; 0, 0, 0, 0, 1, 0, 0, 0, 1; ... . - Eric W. Weisstein, Apr 08 2006
Limit_{n->oo} log(a(n))/n = log(2). - Bret Mulvey, May 17 2008
Equals row sums of triangle A166548; e.g., 17 = (2 + 4 + 6 + 4 + 1). - Gary W. Adamson, Oct 16 2009
Equals row sums of triangle A166555. - Gary W. Adamson, Oct 17 2009
For n >= 1, all terms are in A001969. - Vladimir Shevelev, Oct 25 2010
Let n,m >= 0 be such that no carries occur when adding them. Then a(n+m) = a(n)*a(m). - Vladimir Shevelev, Nov 28 2010
Let phi_a(n) be the number of a(k) <= a(n) and respectively prime to a(n) (i.e., totient function over {a(n)}). Then, for n >= 1, phi_a(n) = 2^v(n), where v(n) is the number of 0's in the binary representation of n. - Vladimir Shevelev, Nov 29 2010
Trisection of this sequence gives rows of A008287 mod 2 converted to decimal. See also A177897, A177960. - Vladimir Shevelev, Jan 02 2011
Converting the rows of the powers of the k-nomial (k = 2^e where e >= 1) term-wise to binary and reading the concatenation as binary number gives every (k-1)st term of this sequence. Similarly with powers p^k of any prime. It might be interesting to study how this fails for powers of composites. - Joerg Arndt, Jan 07 2011
This sequence appears in Pascal's triangle mod 2 in another way, too. If we write it as
1111111...
10101010...
11001100...
10001000...
we get (taking the period part in each row):
.(1) (base 2) = 1
.(10) = 2/3
.(1100) = 12/15 = 4/5
.(1000) = 8/15
The k-th row, treated as a binary fraction, seems to be equal to 2^k / a(k). - Katarzyna Matylla, Mar 12 2011
From Daniel Forgues, Jun 16-18 2011: (Start)
Since there are 5 known Fermat primes, there are 32 products of distinct Fermat primes (thus there are 31 constructible odd-sided polygons, since a polygon has at least 3 sides). a(0)=1 (empty product) and a(1) to a(31) are those 31 non-products of distinct Fermat primes.
It can be proved by induction that all terms of this sequence are products of distinct Fermat numbers (A000215):
a(0)=1 (empty product) are products of distinct Fermat numbers in { };
a(2^n+k) = a(k) * (2^(2^n)+1) = a(k) * F_n, n >= 0, 0 <= k <= 2^n - 1.
Thus for n >= 1, 0 <= k <= 2^n - 1, and
a(k) = Product_{i=0..n-1} F_i^(alpha_i), alpha_i in {0, 1},
this implies
a(2^n+k) = Product_{i=0..n-1} F_i^(alpha_i) * F_n, alpha_i in {0, 1}.
(Cf. OEIS Wiki links below.) (End)
The bits in the binary expansion of a(n) give the coefficients of the n-th power of polynomial (X+1) in ring GF(2)[X]. E.g., 3 ("11" in binary) stands for (X+1)^1, 5 ("101" in binary) stands for (X+1)^2 = (X^2 + 1), and so on. - Antti Karttunen, Feb 10 2016

Examples

			Given a(5)=51, a(6)=85 since a(5) XOR 2*a(5) = 51 XOR 102 = 85.
From _Daniel Forgues_, Jun 18 2011: (Start)
  a(0) = 1 (empty product);
  a(1) = 3 = 1 * F_0 = a(2^0+0) = a(0) * F_0;
  a(2) = 5 = 1 * F_1 = a(2^1+0) = a(0) * F_1;
  a(3) = 15 = 3 * 5 = F_0 * F_1 = a(2^1+1) = a(1) * F_1;
  a(4) = 17 = 1 * F_2 = a(2^2+0) = a(0) * F_2;
  a(5) = 51 = 3 * 17 = F_0 * F_2 = a(2^2+1) = a(1) * F_2;
  a(6) = 85 = 5 * 17 = F_1 * F_2 = a(2^2+2) = a(2) * F_2;
  a(7) = 255 = 3 * 5 * 17 = F_0 * F_1 * F_2 = a(2^2+3) = a(3) * F_2;
  ... (End)

References

  • Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences, Cambridge University Press, 2003, p. 113.
  • Henry Wadsworth Gould, Exponential Binomial Coefficient Series, Tech. Rep. 4, Math. Dept., West Virginia Univ., Morgantown, WV, Sept. 1961.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 136-137.

Links

Crossrefs

Cf. A000079, A000215 (Fermat numbers), A047999, A048720, A054432, A173019, A177882, A177897, A177960, A193231, A230116, A247282, A249184, A268391.
Cf. A038183 (odd bisection, 1D Cellular Automata Rule 90).
Iterates of A048724 (starting from 1).
Row 3 of A048723.
Positions of records in A268389.
Positions of ones in A268669 and A268384 (characteristic function).
Not the same as A045544 nor as A053576.
Cf. A045544.

Programs

  • Haskell
    a001317 = foldr (\u v-> 2*v + u) 0 . map toInteger . a047999_row
-- Reinhard Zumkeller, Nov 24 2012
(Scheme, with memoization-macro definec, two variants)
(definec (A001317 n) (if (zero? n) 1 (A048724 (A001317 (- n 1)))))
(definec (A001317 n) (if (zero? n) 1 (A048720bi 3 (A001317 (- n 1))))) ;; Where A048720bi implements the dyadic function given in A048720.
;; Antti Karttunen, Feb 10 2016
  • Magma
    [&+[(Binomial(n, i) mod 2)*2^i: i in [0..n]]: n in [0..41]]; // Vincenzo Librandi, Feb 12 2016
  • Maple
    A001317 := proc(n) local k; add((binomial(n,k) mod 2)*2^k, k=0..n); end;
  • Mathematica
    a[n_] := Nest[ BitXor[#, BitShiftLeft[#, 1]] &, 1, n]; Array[a, 42, 0] (* Joel Madigan (dochoncho(AT)gmail.com), Dec 03 2007 *)
NestList[BitXor[#,2#]&,1,50] (* Harvey P. Dale, Aug 02 2021 *)
  • PARI
    a(n)=sum(i=0,n,(binomial(n,i)%2)*2^i)
  • PARI
    a=1; for(n=0, 66, print1(a,", "); a=bitxor(a,a<<1) ); \\ Joerg Arndt, Mar 27 2013
  • PARI
    A001317(n,a=1)={for(k=1,n,a=bitxor(a,a<<1));a} \\ M. F. Hasler, Jun 06 2016
  • PARI
    a(n) = subst(lift(Mod(1+'x,2)^n), 'x, 2); \\ Gheorghe Coserea, Nov 09 2017
  • Python
    from sympy import binomial
def a(n): return sum([(binomial(n, i)%2)*2**i for i in range(n + 1)]) # Indranil Ghosh, Apr 11 2017
  • Python
    def A001317(n): return int(''.join(str(int(not(~n&k))) for k in range(n+1)),2) # Chai Wah Wu, Feb 04 2022

Formula

a(n+1) = a(n) XOR 2*a(n), where XOR is binary exclusive OR operator. - Paul D. Hanna, Apr 27 2003
a(n) = Product_{e(j, n) = 1} (2^(2^j) + 1), where e(j, n) is the j-th least significant digit in the binary representation of n (Roberts: see Allouche & Shallit). - Benoit Cloitre, Jun 08 2004
a(2*n+1) = 3*a(2*n). Proof: Since a(n) = Product_{k in K} (1 + 2^(2^k)), where K is the set of integers such that n = Sum_{k in K} 2^k, clearly K(2*n+1) = K(2*n) union {0}, hence a(2*n+1) = (1+2^(2^0))*a(2*n) = 3*a(2*n). - Emmanuel Ferrand and Ralf Stephan, Sep 28 2004
a(32*n) = 3 ^ (32 * n * log(2) / log(3)) + 1. - Bret Mulvey, May 17 2008
For n >= 1, A000120(a(n)) = 2^A000120(n). - Vladimir Shevelev, Oct 25 2010
a(2^n) = A000215(n); a(2^n-1) = a(2^n)-2; for n >= 1, m >= 0,
a(2^(n-1)-1)*a(2^n*m + 2^(n-1)) = 3*a(2^(n-1))*a(2^n*m + 2^(n-1)-2). - Vladimir Shevelev, Nov 28 2010
Sum_{k>=0} 1/a(k) = Product_{n>=0} (1 + 1/F_n), where F_n=A000215(n);
Sum_{k>=0} (-1)^(m(k))/a(k) = 1/2, where {m(n)} is Thue-Morse sequence (A010060).
If F_n is defined by F_n(z) = z^(2^n) + 1 and a(n) by (1/2)*Sum_{i>=0}(1-(-1)^{binomial(n,i)})*z^i, then, for z > 1, the latter two identities hold as well with the replacement 1/2 in the right hand side of the 2nd one by 1-1/z. - Vladimir Shevelev, Nov 29 2010
G.f.: Product_{k>=0} ( 1 + z^(2^k) + (2*z)^(2^k) ). - conjectured by Shamil Shakirov, proved by Vladimir Shevelev
a(n) = A000225(n+1) - A219843(n). - Reinhard Zumkeller, Nov 30 2012
From Antti Karttunen, Feb 10 2016: (Start)
a(0) = 1, and for n > 1, a(n) = A048720(3, a(n-1)) = A048724(a(n-1)).
a(n) = A048723(3,n).
a(n) = A193231(A000079(n)).
For all n >= 0: A268389(a(n)) = n.
(End)

A003558 Least number m > 0 such that 2^m == +-1 (mod 2n + 1).

Original entry on oeis.org

1, 1, 2, 3, 3, 5, 6, 4, 4, 9, 6, 11, 10, 9, 14, 5, 5, 12, 18, 12, 10, 7, 12, 23, 21, 8, 26, 20, 9, 29, 30, 6, 6, 33, 22, 35, 9, 20, 30, 39, 27, 41, 8, 28, 11, 12, 10, 36, 24, 15, 50, 51, 12, 53, 18, 36, 14, 44, 12, 24, 55, 20, 50, 7, 7, 65, 18, 36, 34, 69, 46
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Multiplicative suborder of 2 (mod 2n+1) (or sord(2, 2n+1)).
This is called quasi-order of 2 mod b, with b = 2*n+1, for n >= 1, in the Hilton/Pederson reference.
For the complexity of computing this, see A002326.
Also, the order of the so-called "milk shuffle" of a deck of n cards, which maps cards (1,2,...,n) to (1,n,2,n-1,3,n-2,...). See the paper of Lévy. - Jeffrey Shallit, Jun 09 2019
It appears that under iteration of the base-n Kaprekar map, for even n > 2 (A165012, A165051, A165090, A151949 in bases 4, 6, 8, 10), almost all cycles are of length a(n/2 - 1); proved under the additional constraint that the cycle contains at least one element satisfying "number of digits (n-1) - number of digits 0 = o(total number of digits)". - Joseph Myers, Sep 05 2009
From Gary W. Adamson, Sep 20 2011: (Start)
a(n) can be determined by the cycle lengths of iterates using x^2 - 2, seed 2*cos(2*Pi/N); as shown in the A065941 comment of Sep 06 2011. The iterative map of the logistic equation 4x*(1-x) is likewise chaotic with the same cycle lengths but initiating the trajectory with sin^2(2*Pi/N), N = 2n+1 [Kappraff & Adamson, 2004]. Chaotic terms with the identical cycle lengths can be obtained by applying Newton's method to i = sqrt(-1) [Strang, also Kappraff and Adamson, 2003], resulting in the morphism for the cot(2*Pi/N) trajectory: (x^2-1)/2x. (End)
From Gary W. Adamson, Sep 11 2019: (Start)
Using x^2 - 2 with seed 2*cos(Pi/7), we obtain the period-three trajectory 1.8019377...-> 1.24697...-> -0.445041... For an odd prime N, the trajectory terms represent diagonal lengths of regular star 2N-gons, with edge the shortest value (0.445... in this case.) (Cf. "Polygons and Chaos", p. 9, Fig 4.) We can normalize such lengths by dividing through with the lowest value, giving 3 diagonals of the 14-gon: (1, 2.801937..., 4.048917...). Label the terms ranked in magnitude with odd integers (1, 3, 5), and we find that the diagonal lengths are in agreement with the diagonal formula (sin(j*Pi)/14)/(sin(Pi/14)), with j = (1,3,5). (End)
Roots of signed n-th row A054142 polynomials are chaotic with respect to the operation (-2, x^2), with cycle lengths a(n). Example: starting with a root to x^3 - 5x^2 + 6x - 1 = 0; (2 + 2*cos(2*Pi/N) = 3.24697...); we obtain the trajectory (3.24697...-> 1.55495...-> 0.198062...); the roots to the polynomial with cycle length 3 matching a(3) = 3. - Gary W. Adamson, Sep 21 2011
From Juhani Heino, Oct 26 2015: (Start)
Start a sequence with numbers 1 and n. For next numbers, add previous numbers going backwards until the sum is even. Then the new number is sum/2. I conjecture that the sequence returns to 1,n and a(n) is the cycle length.
For example:
1,7,4,2,1,7,... so a(7) = 4.
1,6,3,5,4,2,1,6,... so a(6) = 6. (End)
From Juhani Heino, Nov 06 2015: (Start)
Proof of the above conjecture: Let n = -1/2; thus 2n + 1 = 0, so operations are performed mod (2n + 1). When the member is even, it is divided by 2. When it is odd, multiply by n, so effectively divide by -2. This is all well-defined in the sense that new members m are 1 <= m <= n. Now see what happens starting from an odd member m. The next member is -m/2. As long as there are even members, divide by 2 and end up with an odd -m/(2^k). Now add all the members starting with m. The sum is m/(2^k). It's divided by 2, so the next member is m/(2^(k+1)). That is the same as (-m/(2^k))/(-2), as with the definition.
So actually start from 1 and always divide by 2, although the sign sometimes changes. Eventually 1 is reached again. The chain can be traversed backwards and then 2^(cycle length) == +-1 (mod 2n + 1).
To conclude, we take care of a(0): sequence 1,0 continues with zeros and never returns to 1. So let us declare that cycle length 0 means unavailable. (End)
From Gary W. Adamson, Aug 20 2019: (Start)
Terms in the sequence can be obtained by applying the doubling sequence mod (2n + 1), then counting the terms until the next term is == +1 (mod 2n + 1). Example: given 25, the trajectory is (1, 2, 4, 8, 16, 7, 14, 3, 6, 12).
The cycle ends since the next term is 24 == -1 (mod 25) and has a period of 10. (End)
From Gary W. Adamson, Sep 04 2019: (Start)
Conjecture of Kappraff and Adamson in "Polygons and Chaos", p. 13 Section 7, "Chaos and Number": Given the cycle length for N = 2n + 1, the same cycle length is present in bases 4, 9, 16, 25, ..., m^2, for the expansion of 1/N.
Examples: The cycle length for 7 is 3, likewise for 1/7 in base 4: 0.021021021.... In base 9 the expansion of 1/7 is 0.125125125... Check: The first few terms are 1/9 + 2/81 + 5/729 = 104/279 = 0.1426611... (close to 1/7 = 0.142857...). (End)
From Gary W. Adamson, Sep 24 2019: (Start)
An exception to the rule for 1/N in bases m^2: (when N divides m^2 as in 1/7 in base 49, = 7/49, rational). When all terms in the cycle are the same, the identity reduces to 1/N in (some bases) = .a, a, a, .... The minimal values of "a" for 1/N are provided as examples, with the generalization 1/N in base (N-1)^2 = .a, a, a, ... for N odd:
1/3 in base 4 = .1, 1, 1, ...
1/5 in base 16 = .3, 3, 3, ...
1/7 in base 36 = .5, 5, 5, ...
1/9 in base 64 = .7, 7, 7, ...
1/11 in base 100 = .9, 9, 9, ... (Check: the first three terms are 9/100 +9/(100^2) + 9/(100^3) = 0.090909 where 1/11 = 0.09090909...). (End)
For N = 2n+1, the corresponding entry is equal to the degree of the polynomial for N shown in (Lang, Table 2, p. 46). As shown, x^3 - 3x - 1 is the minimal polynomial for N = 9, with roots (1.87938..., -1.53208..., 0.347296...); matching the (abs) values of the 2*cos(Pi/9) trajectory using x^2 - 2. Thus, a(4) = 3. If N is prime, the polynomials shown in Table 2 are the same as those for the same N in A065941. If different, the minimal polynomials shown in Table 2 are factors of those in A065941. - Gary W. Adamson, Oct 01 2019
The terms in the 2*cos(Pi/N) trajectory (roots to the minimal polynomials in A187360 and (Lang)), are quickly obtained from the doubling trajectory (mod N) by using the operation L(m) 2*cos(x)--> 2*cos(m*x), where L(2), the second degree Lucas polynomial (A034807) is x^2 - 2. Relating to the heptagon and using seed 2*cos(Pi/7), we obtain the trajectory 1.8019..., 1.24697..., and 0.445041....; cyclic with period 3. All such roots can be derived from the N-th roots of Unity and can be mapped on the Vesica Piscis. Given the roots of Unity (Polar 1Angle(k*2*Pi/N), k = 1, 2, ..., (N-1)/2) the Vesica Piscis maps these points on the left (L) circle to the (R) circle by adding 1A(0) or (a + b*I) = (1 + 0i). But this operation is the same as vector addition in which the resultant vector is 1 + 1A(k*(2*Pi/N)). Example: given the radius at 2*Pi/7 on the left circle, this maps to (1 + 1A(2*Pi/7)) on the right circle; or 1A(2*Pi/7) --> (1.8019377...A(Pi/7). Similarly, 1 + 1A((2)*2*Pi/7)) maps to (1.24697...A (2*Pi/7); and 1 + 1A(3*2*Pi/7) maps to (.0445041...A(3*Pi/7). - Gary W. Adamson, Oct 23 2019
From Gary W. Adamson, Dec 01 2021: (Start)
As to segregating the two sets: (A014659 terms are those N = (2*n+1), N divides (2^m - 1), and (A014657 terms are those N that divide (2^m + 1)); it appears that the following criteria apply: Given IcoS(N, 1) (cf. Lang link "On the Equivalence...", p. 16, Definition 20), if the number of odd terms is odd, then N belongs to A014659, otherwise A014657. In IcoS(11, 1): (1, 2, 4, 3, 5), three odd terms indicate that 11 is a term in A014657. IcoS(15, 1) has the orbit (1, 2, 4, 7) with two odd terms indicating that 15 is a term in A014659.
It appears that if sin(2^m * Pi/N) has a negative sign, then N is in A014659; otherwise N is in A014657. With N = 15, m is 4 and sin(16 * Pi/15) is -0.2079116... If N is 11, m is 5 and sin(32 * Pi/11) is 0.2817325. (End)
On the iterative map using x^2 - 2, (Devaney, p. 126) states that we must find the function that takes 2*cos(Pi) -> 2*cos(2*Pi). "However, we may write 2*cos(2*Pi) = 2*(2*cos^2(Pi) - 1) = (2*cos(Pi))^2 - 2. So the required function is x^2 - 2." On the period 3 implies chaos theorem of James Yorke and T.Y. Li, proved in 1975; Devaney (p. 133) states that if F is continuous and we find a cycle of period 3, there are infinitely many other cycles for this map with every possible period. Check: The x^2 - 2 orbit for 7 has a period of 3, so this entry has periodic points of all other periods. - Gary W. Adamson, Jan 04 2023
It appears that a(n) is the length of the cycle starting at 2/(2*n+1) for the map x->1 - abs(2*x-1). - Michel Marcus, Jul 16 2025

Examples

			a(3) = 3 since f(x) = x^2 - 2 has a period of 3 using seed 2*cos(2*Pi/7), where 7 = 2*3 + 1.
a(15) = 5 since the iterative map of the logistic equation 4x*(1-x) has a period 5 using seed sin^2(2*Pi)/N; N = 31 = 2*15 + 1.

References

  • Peter Hilton and Jean Pedersen, A Mathematical Tapestry: Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, 2010, pp. 261-264.
  • Carl Schick, Trigonometrie und unterhaltsame Zahlentheorie, Bokos Druck, Zürich, 2003 (ISBN 3-9522917-0-6).
  • Robert L. Devaney, A First Course in Chaotic Dynamical Systems, Theory and Experiment; Perseus Books Publishing, 1992, pp. 121-126.

Links

Crossrefs

Cf. A054142, A065941, A085478, A160657, A179480, A135303 (coach numbers), A216371 (odd primes with one coach), A000215 (Fermat numbers).
A216066 is an essentially identical sequence apart from the offset.
Cf. A329593, A332433 (signs).
Cf. A014657, A014659.

Programs

  • Maple
    A003558 := proc(n)
    local m,mo ;
    if n = 0 then
        return 0 ;
    end if;
    for m from 1 do
        mo := modp(2^m,2*n+1) ;
        if mo in {1,2*n} then
            return m;
        end if;
    end do:
end proc:
seq(A003558(n),n=0..20) ; # R. J. Mathar, Dec 01 2014
f:= proc(n) local t;
      t:= numtheory:-mlog(-1,2,n);
      if t = FAIL then numtheory:-order(2,n) else t fi
end proc:
0, seq(f(2*k+1),k=1..1000); # Robert Israel, Oct 26 2015
  • Mathematica
    Suborder[a_,n_]:=If[n>1&&GCD[a,n]==1,Min[MultiplicativeOrder[a,n,{-1,1}]],0];
Join[{1},Table[Suborder[2,2n+1],{n,100}]] (* T. D. Noe, Aug 02 2006 *) (* revised by Vincenzo Librandi, Apr 11 2020 *)
  • PARI
    a(n) = {m=1; while(m, if( (2^m) % (2*n+1) == 1 || (2^m) % (2*n+1) == 2*n, return(m)); m++)} \\ Altug Alkan, Nov 06 2015
  • PARI
    isok(m, n) = my(md = Mod(2, 2*n+1)^m); (md==1) || (md==-1);
A003558(n) = my(m=1); while(!isok(m,n) , m++); m; \\ Michel Marcus, May 06 2020
  • Python
    def A003558(n):
    m, k = 1, 2 % (c:=(r:=n<<1)+1)
    while not (k==1 or k==r):
        k = 2*k%c
        m += 1
    return m # Chai Wah Wu, Oct 09 2023

Formula

a(n) = log_2(A160657(n) + 2) - 1. - Nathaniel Johnston, May 22 2009
a(n-1) = card {cos((2^k)*Pi/(2*n-1)): k in N} for n >= 1 (see A216066, an essentially identical sequence, for more information). - Roman Witula, Sep 01 2012
a(n) <= n. - Charles R Greathouse IV, Sep 15 2012 [For n >= 1]
a(n) = min{k > 0 | q_k = q_0} where q_0 = 1 and q_k = |2*n+1 - 2*q_{k-1}| (cf. [Schick, p. 4]; q_k=1 for n=1; q_k=A010684(k) for n=2; q_k=A130794(k) for n=3; q_k=|A154870(k-1)| for n=4; q_k=|A135449(k)| for n=5.) - Jonathan Skowera, Jun 29 2013
2^(a(n)) == A332433(n) (mod (2*n+1)), and (2^(a(n)) - A332433(n))/(2*n+1) = A329593(n), for n >= 0. - Wolfdieter Lang, Apr 09 2020

Extensions

More terms from Harry J. Smith, Feb 11 2005
Entry revised by N. J. A. Sloane, Aug 02 2006 and again Dec 10 2017

A156695 Odd numbers that are not of the form p + 2^a + 2^b, a, b > 0, p prime.

Original entry on oeis.org

1, 3, 5, 6495105, 848629545, 1117175145, 2544265305, 3147056235, 3366991695, 3472109835, 3621922845, 3861518805, 4447794915, 4848148485, 5415281745, 5693877405, 6804302445, 7525056375, 7602256605, 9055691835, 9217432215
Offset: 1

Views

Author

Charles R Greathouse IV, Feb 13 2009

Keywords

Comments

Crocker shows that this sequence is infinite.
All members above 5 found so far (up to 2.5 * 10^11) are divisible by 255 = 3 * 5 * 17, and many are divisible by 257. I conjecture that all members of this sequence greater than 5 are divisible by 255. This implies that all odd numbers (greater than 7) are the sum of a prime and at most three positive powers of two.
Pan shows that, for every c > 1, a(n) << x^c. More specifically, there are constants C,D > 0 such that there are at least Dx/exp(C log x log log log log x/log log log x) members of this sequence up to x. - Charles R Greathouse IV, Apr 11 2016
All terms > 5 are numbers k > 3 such that k - 2^n is a de Polignac number (A006285) for every n > 0 with 2^n < k. Are there numbers K such that |K - 2^n| is a Riesel number (A101036) for every n > 0? If so, ||K - 2^n| - 2^m| is composite for every pair m,n > 0, by the dual Riesel conjecture. - Thomas Ordowski, Jan 06 2024
In keeping with the example's connection to A000215, the lowest ki for ki * Product_{i=0..11} (F(i)) to belong to A156695 are 1, 433007, 25471, 17047, 1291, 7, 101, 807, 83, 347, 9, 179. So for example, 433007*(3*5) is a term. This implies a variant of the first commented conjecture accordingly. - Bill McEachen, Apr 17 2025

Examples

			Prime factorization of terms:
F_0 = 3, F_1 = 5, F_2 = 17, F_3 = 257 are Fermat numbers (cf. A000215)
6495105    = 3   * 5   * 17               * 25471
848629545  = 3   * 5   * 17               * 461      * 7219
1117175145 = 3   * 5   * 17         * 257 * 17047
2544265305 = 3^2 * 5   * 17         * 257 * 12941
3147056235 = 3^2 * 5   * 17         * 257 * 16007
3366991695 = 3   * 5   * 17   * 83  * 257 * 619
3472109835 = 3   * 5   * 17         * 257 * 52981
3621922845 = 3   * 5   * 17^2       * 257 * 3251
3861518805 = 3^3 * 5   * 17         * 257 * 6547
4447794915 = 3^3 * 5   * 17         * 257 * 7541
4848148485 = 3^4 * 5   * 17               * 704161
5415281745 = 3   * 5   * 17               * 21236399
5693877405 = 3^2 * 5   * 17         * 257 * 28961
6804302445 = 3^2 * 5   * 17   * 53  * 257 * 653
7525056375 = 3^2 * 5^3 * 17         * 257 * 1531
7602256605 = 3   * 5   * 17         * 257 * 311      * 373
9055691835 = 3   * 5   * 17         * 257 * 138181
9217432215 = 3^2 * 5   * 17   * 173 * 257 * 271

Links

Crossrefs

Cf. A006285, A118955, A232565, A337487.

Programs

  • PARI
    is(n)=if(n%2==0,return(0)); for(a=1,log(n)\log(2), for(b=1,a, if(isprime(n-2^a-2^b),return(0)))); 1 \\ Charles R Greathouse IV, Nov 27 2013
  • Python
    from itertools import count, islice
from sympy import isprime
def A156695_gen(startvalue=1): # generator of terms >= startvalue
    for n in count(max(startvalue+(startvalue&1^1),1),2):
        l = n.bit_length()-1
        for a in range(l,0,-1):
            c = n-(1<A156695_list = list(islice(A156695_gen(),4)) # Chai Wah Wu, Nov 29 2023

Extensions

Factorizations added by Daniel Forgues, Jan 20 2011

A092506 Prime numbers of the form 2^n + 1.

Original entry on oeis.org

2, 3, 5, 17, 257, 65537
Offset: 1

Views

Author

Jorge Coveiro, Apr 05 2004

Keywords

Comments

2 together with the Fermat primes A019434.
Obviously if 2^n + 1 is a prime then either n = 0 or n is a power of 2. - N. J. A. Sloane, Apr 07 2004
Numbers m > 1 such that 2^(m-2) divides (m-1)! and m divides (m-1)! + 1. - Thomas Ordowski, Nov 25 2014
From Jaroslav Krizek, Mar 06 2016: (Start)
Also primes p such that sigma(p-1) = 2p - 3.
Also primes of the form 2^n + 3*(-1)^n - 2 for n >= 0 because for odd n, 2^n - 5 is divisible by 3.
Also primes of the form 2^n + 6*(-1)^n - 5 for n >= 0 because for odd n, 2^n - 11 is divisible by 3.
Also primes of the form 2^n + 15*(-1)^n - 14 for n >= 0 because for odd n, 2^n - 29 is divisible by 3. (End)
Exactly the set of primes p such that any number congruent to a primitive root (mod p) must have at least one prime divisor that is also congruent to a primitive root (mod p). See the links for a proof. - Rafay A. Ashary, Oct 13 2016
Conjecture: these are the only solutions to the equation A000010(x)+A000010(x-1)=floor((3x-2)/2). - Benoit Cloitre, Mar 02 2018
For n > 1, if 2^n + 1 divides 3^(2^(n-1)) + 1, then 2^n + 1 is a prime. - Jinyuan Wang, Oct 13 2018
The prime numbers occurring in A003401. Also, the prime numbers dividing at least one term of A003401. - Jeppe Stig Nielsen, Jul 24 2019

Links

Crossrefs

A019434 is the main entry for these numbers.
Cf. A000010, A000040, A000051, A000215, A003401.

Programs

  • GAP
    Filtered(List([1..20],n->2^n+1),IsPrime); # Muniru A Asiru, Oct 25 2018
  • Magma
    [2^n + 1 : n in [0..25] | IsPrime(2^n+1)]; // Vincenzo Librandi, Oct 14 2018
  • Mathematica
    Select[2^Range[0,100]+1,PrimeQ] (* Harvey P. Dale, Aug 02 2015 *)
  • PARI
    print1(2); for(n=0,9, if(ispseudoprime(t=2^2^n+1), print1(", "t))) \\ Charles R Greathouse IV, Aug 29 2016

A023394 Prime factors of Fermat numbers.

Original entry on oeis.org

3, 5, 17, 257, 641, 65537, 114689, 274177, 319489, 974849, 2424833, 6700417, 13631489, 26017793, 45592577, 63766529, 167772161, 825753601, 1214251009, 6487031809, 70525124609, 190274191361, 646730219521, 2710954639361, 2748779069441, 4485296422913, 6597069766657
Offset: 1

Views

Author

David W. Wilson

Keywords

Comments

Is it true that this sequence consists of the odd primes p with 2^(2^p) == 1 (mod p)? (David Wilson, Jul 31 2008). Answer from Max Alekseyev: Yes! If prime p divides Fm = 2^(2^m)+1, then 2^(2^(m+1)) == 1 (mod p) and p is of the form p = k*2^(m+2)+1 > m+1. Squaring the last congruence p-(m+1) times, we get 2^(2^p) == 1 (mod p). On the other hand, if 2^(2^p) == 1 (mod p) for prime p, consider a sequence 2^(2^0), 2^(2^1), 2^(2^2), ..., 2^(2^p). Modulo p this sequence ends with a bunch of 1's but just before the first 1 we must see -1 (as the only other square root of 1 modulo prime p), i.e. for some m, 2^(2^m) == -1 (mod p), implying that p divides Fermat number 2^(2^m) + 1.
Also primes p such that the multiplicative order of 2 (mod p) is a power of 2. A theorem of Lucas states that if m>1 and prime p divides 1+2^2^m (the m-th Fermat number), then p = 1+k*2^(m+2) for some integer k. - T. D. Noe, Jan 29 2009
Wilfrid Keller analyzed the current status of the search for prime factors of Fermat number and stated that all prime factors less than 10^19 are now known. He sent me terms a(25) to a(50). - T. D. Noe, Feb 01 2009, Feb 03 2009, Jan 14 2013
Křížek, Luca, & Somer (2002) show that the sum of the reciprocals of this sequence converge, answering a question of Golomb (1955). - Charles R Greathouse IV, Jul 15 2013
To test if a prime p is a member, it suffices to check if the multiplicative order of 2 modulo p is a power of two. But it is obvious that the order is a divisor of p-1. Therefore it is enough to test if 2^(2^j) == 1 (mod p) where 2^j is the largest power of two that divides p-1. - Jeppe Stig Nielsen, Mar 13 2022
Primes p such that 2^(2^p) == 2^p - 1 (mod p); i.e., prime numbers in A373580. - Thomas Ordowski, Jun 11 2024

References

  • Michal Krížek, Florian Luca and Lawrence Somer, 17 Lectures on Fermat Numbers, Springer-Verlag NY 2001.

Links

Crossrefs

Supersequence of A229851.
Cf. A000215, A344784.

Programs

  • Maple
    q:=p->(isprime(p) and irem(2^(2^padic:-ordp(p-1, 2))-1, p) = 0):
select(q, [$1..10^5])[]; # Lorenzo Sauras Altuzarra, Feb 20 2023
  • Mathematica
    Select[Prime[Range[100000]],IntegerQ[Log[2,MultiplicativeOrder[2,# ]]]&] (* T. D. Noe, Jan 29 2009 *)
  • PARI
    is(p)=p>2 && Mod(2,p)^lift(Mod(2,znorder(Mod(2,p)))^p)==1 && isprime(p) \\ Charles R Greathouse IV, Feb 04 2013
  • PARI
    my(isfermatdivisor(m)=if(m>0, if(m==1, return(1), v=valuation(m-1, 2); c=0; if(m>2, e=logint(m-1, 2); if(e==v&&Mod(m-1, e)==0, t=logint(v, 2); c=1)); if(v>6&&c==0, x=2; t=0; for(i=0, v-2, if(x+1==m, c=1; break); s=x*x; x=s-s\m*m; t++)); if(c==1, print((m-1)/2^v"*2^"v" + 1 divides 2^(2^"t") + 1")); return(c)))); L=List([]); forstep(m=3, 63766529, 2, if(isprime(m)&&isfermatdivisor(m), listput(L, m))); print(); print(Vec(L)); \\ Arkadiusz Wesolowski, Jan 16 2018
  • PARI
    forprime(p=2,,Mod(2,p)^(2^valuation(p-1,2))==1&&print1(p,", ")) \\ Jeppe Stig Nielsen, Mar 13 2022

Formula

a(n) is a prime factor of the Fermat number 1+2^2^A023395(n). - T. D. Noe, Feb 01 2009
a(n) >> n^2 log^2 n, see Křížek, Luca, & Somer. - Charles R Greathouse IV, Jul 16 2013
Sum_{n>=1} 1/a(n) = A344784. - Amiram Eldar, May 30 2021

A003401 Numbers of edges of regular polygons constructible with ruler (or, more precisely, an unmarked straightedge) and compass.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40, 48, 51, 60, 64, 68, 80, 85, 96, 102, 120, 128, 136, 160, 170, 192, 204, 240, 255, 256, 257, 272, 320, 340, 384, 408, 480, 510, 512, 514, 544, 640, 680, 768, 771, 816, 960, 1020, 1024, 1028, 1088, 1280, 1285
Offset: 1

Views

Author

N. J. A. Sloane, R. K. Guy

Keywords

Comments

The terms 1 and 2 correspond to degenerate polygons.
These are also the numbers for which phi(n) is a power of 2: A209229(A000010(a(n))) = 1. - Olivier Gérard Feb 15 1999
From Stanislav Sykora, May 02 2016: (Start)
The sequence can be also defined as follows: (i) 1 is a member. (ii) Double of any member is also a member. (iii) If a member is not divisible by a Fermat prime F_k then its product with F_k is also a member. In particular, the powers of 2 (A000079) are a subset and so are the Fermat primes (A019434), which are the only odd prime members.
The definition is too restrictive (though correct): The Georg Mohr - Lorenzo Mascheroni theorem shows that constructibility using a straightedge and a compass is equivalent to using compass only. Moreover, Jean Victor Poncelet has shown that it is also equivalent to using straightedge and a fixed ('rusty') compass. With the work of Jakob Steiner, this became part of the Poncelet-Steiner theorem establishing the equivalence to using straightedge and a fixed circle (with a known center). A further extension by Francesco Severi replaced the availability of a circle with that of a fixed arc, no matter how small (but still with a known center).
Constructibility implies that when m is a member of this sequence, the edge length 2*sin(Pi/m) of an m-gon with circumradius 1 can be written as a finite expression involving only integer numbers, the four basic arithmetic operations, and the square root. (End)
If x,y are terms, and gcd(x,y) is a power of 2 then x*y is also a term. - David James Sycamore, Aug 24 2024

Examples

			34 is a term of this sequence because a circle can be divided into exactly 34 parts. 7 is not.

References

  • Albert H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 183.
  • Allan Clark, Elements of Abstract Algebra, Chapter 4, Galois Theory, Dover Publications, NY 1984, page 124.
  • Duane W. DeTemple, "Carlyle circles and the Lemoine simplicity of polygon constructions." The American Mathematical Monthly 98.2 (1991): 97-108. - N. J. A. Sloane, Aug 05 2021
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • B. L. van der Waerden, Modern Algebra. Unger, NY, 2nd ed., Vols. 1-2, 1953, Vol. 1, p. 187.

Links

Crossrefs

Subsequence of A295298. - Antti Karttunen, Nov 27 2017
A004729 and A051916 are subsequences. - Reinhard Zumkeller, Mar 20 2010
Cf. A000079, A004169, A000215, A099884, A019434 (Fermat primes).
Edge lengths of other constructible m-gons: A002194 (m=3), A002193 (4), A182007 (5), A101464 (8), A094214 (10), A101263 (12), A272534 (15), A272535 (16), A228787 (17), A272536 (20).
Positions of zeros in A293516 (apart from two initial -1's), and in A336469, positions of ones in A295660 and in A336477 (characteristic function).
Cf. also A046528.
Cf. A000079, A092506.

Programs

  • Haskell
    a003401 n = a003401_list !! (n-1)
a003401_list = map (+ 1) $ elemIndices 1 $ map a209229 a000010_list
-- Reinhard Zumkeller, Jul 31 2012
  • Mathematica
    Select[ Range[ 1300 ], IntegerQ[ Log[ 2, EulerPhi[ # ] ] ]& ] (* Olivier Gérard Feb 15 1999 *)
(* first do *) Needs["DiscreteMath`Combinatorica`"] (* then *) Take[ Union[ Flatten[ NestList[2# &, Times @@@ Table[ UnrankSubset[n, Join[{1}, Table[2^2^i + 1, {i, 0, 4}]]], {n, 63}], 11]]], 60] (* Robert G. Wilson v, Jun 11 2005 *)
nn=10; logs=Log[2,{2,3,5,17,257,65537}]; lim2=Floor[nn/logs[[1]]]; Sort[Reap[Do[z={i,j,k,l,m,n}.logs; If[z<=nn, Sow[2^z]], {i,0,lim2}, {j,0,1}, {k,0,1}, {l,0,1}, {m,0,1}, {n,0,1}]][[2,1]]]
A092506 = {2, 3, 5, 17, 257, 65537}; s = Sort[Times @@@ Subsets@ A092506]; mx = 1300; Union@ Flatten@ Table[(2^n)*s[[i]], {i, 64}, {n, 0, Log2[mx/s[[i]]]}] (* Robert G. Wilson v, Jul 28 2014 *)
  • PARI
    for(n=1,10^4,my(t=eulerphi(n));if(t/2^valuation(t,2)==1,print1(n,", "))); \\ Joerg Arndt, Jul 29 2014
  • PARI
    is(n)=n>>=valuation(n,2); if(n<7, return(n>0)); my(k=logint(logint(n,2),2)); if(k>32, my(p=2^2^k+1); if(n%p, return(0)); n/=p; unknown=1; if(n%p==0, return(0)); p=0; if(is(n)==0, 0, "unknown [has large Fermat number in factorization]"), 4294967295%n==0) \\ Charles R Greathouse IV, Jan 09 2022
  • PARI
    is(n)=n>>=valuation(n,2); 4294967295%n==0 \\ valid for n <= 2^2^33, conjecturally valid for all n; Charles R Greathouse IV, Jan 09 2022
  • Python
    from sympy import totient
A003401_list = [n for n in range(1,10**4) if format(totient(n),'b').count('1') == 1]
# Chai Wah Wu, Jan 12 2015

Formula

Terms from 3 onward are computable as numbers such that cototient-of-totient equals the totient-of-totient: Flatten[Position[Table[co[eu[n]]-eu[eu[n]], {n, 1, 10000}], 0]] eu[m]=EulerPhi[m], co[m]=m-eu[m]. - Labos Elemer, Oct 19 2001, clarified by Antti Karttunen, Nov 27 2017
Any product of 2^k and distinct Fermat primes (primes of the form 2^(2^m)+1). - Sergio Pimentel, Apr 30 2004, edited by Franklin T. Adams-Watters, Jun 16 2006
If the well-known conjecture that there are only five prime Fermat numbers F_k=2^{2^k}+1, k=0,1,2,3,4 is true, then we have exactly: Sum_{n>=1} 1/a(n)= 2*Product_{k=0..4} (1+1/F_k) = 4869735552/1431655765 = 3.40147098978.... - Vladimir Shevelev and T. D. Noe, Dec 01 2010
log a(n) >> sqrt(n); if there are finitely many Fermat primes, then log a(n) ~ k log n for some k. - Charles R Greathouse IV, Oct 23 2015

Extensions

Definition clarified by Bill Gosper. - N. J. A. Sloane, Jun 14 2020

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

Original entry on oeis.org

1, 3, 15, 255, 65535, 4294967295, 18446744073709551615, 340282366920938463463374607431768211455, 115792089237316195423570985008687907853269984665640564039457584007913129639935
Offset: 0

Views

Author

Alan DeKok (aland(AT)ox.org)

Keywords

Comments

In a tree with binary nodes (0, 1 children only), the maximum number of unique child nodes at level n.
Number of binary trees (each vertex has 0, or 1 left, or 1 right, or 2 children) such that all leaves are at level n. Example: a(1) = 3 because we have (i) root with a left child, (ii) root with a right child and (iii) root with two children. a(n) = A000215(n) - 2. - Emeric Deutsch, Jan 20 2004
Similarly, this is also the number of full balanced binary trees of height n. (There is an obvious 1-to-1 correspondence between the two sets of trees.) - David Hobby (hobbyd(AT)newpaltz.edu), May 02 2010
Partial products of A000215.
The first 5 terms n (only) have the property that phi(n)=(n+1)/2, where phi(n) = A000010(n) is Euler's totient function. - Lekraj Beedassy, Feb 12 2007
If A003558(n) is of the form 2^n and A179480(n+1) is even, then (2^(A003558(n)) - 1) is in A051179. Example: A003558(25) = 8 with A179480(25) = 4, even. Then (2^8 - 1) = 255. - Gary W. Adamson, Aug 20 2012
For any odd positive a(0), the sequence defined by a(n) = a(n-1) * (a(n-1) + 2) gives a constructive proof that there exist integers with at least n distinct prime factors, e.g., a(n), since omega(a(n)) >= n. As a corollary, this gives a constructive proof of Euclid's theorem stating that there are infinitely many primes. - Daniel Forgues, Mar 07 2017
From Sergey Pavlov, Apr 24 2017: (Start)
I conjecture that, for n > 7, omega(a(n)) > omega(a(n-1)) > n.
It seems that the largest prime divisor p(n+1) of a(n+1) is always bigger than the largest prime divisor of a(n): p(n+1) > p(n). For 3 < n < 8, p(n+1) > 100 * p(n).
(End)
It appears that a(n) is the integer whose bits indicate the possible subset sums of the first n powers of two. For another example, see the calculation for primes at A368491 - Yigit Oktar, Mar 20 2025

Examples

			15 = 3*5; 255 = 3*5*17; 65535 = 3*5*17*257; ... - _Daniel Forgues_, Mar 07 2017

References

  • M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 1999; see p. 4.

Links

Crossrefs

Cf. A001146, A007018, A048649.
Cf. A003558, A179480, A000215.
Cf. A368491

Programs

Formula

a(n) = A000215(n) - 2.
a(n) = (a(n-1) + 1)^2 - 1, a(0) = 1. [ or a(n) = a(n-1)(a(n-1) + 2) ].
1 = 2/3 + 4/15 + 16/255 + 256/65535 + ... = Sum_{n>=0} A001146(n)/a(n+1) with partial sums: 2/3, 14/15, 254/255, 65534/65535, ... - Gary W. Adamson, Jun 15 2003
a(n) = b(n-1) where b(1)=1, b(n) = Product_{k=1..n-1} (b(k) + 2). - Benoit Cloitre, Sep 13 2003
A136308(n) = A007088(a(n)). - Jason Kimberley, Dec 19 2012
A000215(n) = a(n+1) / a(n). - Daniel Forgues, Mar 07 2017
Sum_{n>=0} 1/a(n) = A048649. - Amiram Eldar, Oct 27 2020
Previous Showing 21-30 of 245 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.