A001146 - OEIS

%I M1297 N0497 #173 Oct 14 2024 02:57:51

%S 2,4,16,256,65536,4294967296,18446744073709551616,

%T 340282366920938463463374607431768211456,

%U 115792089237316195423570985008687907853269984665640564039457584007913129639936

%N a(n) = 2^(2^n).

%C Or, write previous term in base 2, read in base 4.

%C a(1) = 2, a(n) = smallest power of 2 which does not divide the product of all previous terms.

%C Number of truth tables generated by Boolean expressions of n variables. - C. Bradford Barber (bradb(AT)shore.net), Dec 27 2005

%C From _Ross Drewe_, Feb 13 2008: (Start)

%C 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.

%C 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)

%C From _José María Grau Ribas_, Jan 19 2012: (Start)

%C   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]

%C a(n) is the highest value k such that A173419(k) = n+1. - _Charles R Greathouse IV_, Oct 03 2012

%C 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

%C 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

%C 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

%C Erdős has shown that it is an irrationality sequence (see Guy reference). - _Stefano Spezia_, Oct 13 2024

%D R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section E24.

%D D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Vincenzo Librandi, <a href="/A001146/b001146.txt">Table of n, a(n) for n = 0..11</a>

%H A. V. Aho and N. J. A. Sloane, <a href="https://www.fq.math.ca/Scanned/11-4/aho-a.pdf">Some doubly exponential sequences</a>, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437, <a href="http://neilsloane.com/doc/doubly.html">alternative link</a>.

%H Jan Brandts and Apo Cihangir, <a href="https://doi.org/10.1515/spma-2017-0014">Enumeration and investigation of acute 0/1-simplices modulo the action of the hyperoctahedral group</a>, Special Matrices, Vol. 5, No. 1 (2017), pp. 158-201, <a href="http://arxiv.org/abs/1512.03044">arXiv preprint</a>, arXiv:1512.03044 [math.CO], 2015.

%H John H. Conway, <a href="https://doi.org/10.1007/978-3-0348-9078-6_7">Sphere packings, lattices, codes and greed</a>, pp. 45-55 of Proc. Intern. Congr. Math., Vol. 2, 1994, <a href="https://web.archive.org/web/20171111163030/http://www.mathunion.org/ICM/ICM1994.1/Main/icm1994.1.0045.0056.ocr.pdf">alternative link</a>.

%H Jose María Grau and A. M. Oller-Marcén <a href="http://arxiv.org/abs/1203.4066">On the last digit and the last non-zero digit of n^n in base b</a>, arXiv:1203.4066 [math.NT], 2012.

%H Richard K. Guy and J. L. Selfridge, <a href="http://www.jstor.org/stable/2319392">The nesting and roosting habits of the laddered parenthesis</a>, Amer. Math. Monthly 80 (8) (1973), 868-876.

%H Rudolf Ondrejka, <a href="http://dx.doi.org/10.1090/S0025-5718-69-99644-6">Exact values of 2^n, n=1(1)4000</a>, Math. Comp., 23 (1969), 456.

%H Rudolf Ondrejka, <a href="/A000522/a000522.pdf">Letter to N. J. A. Sloane, May 15 1976</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IrrationalitySequence.html">Irrationality Sequence</a>, <a href="http://mathworld.wolfram.com/QuadraticRecurrenceEquation.html">Quadratic Recurrence Equation</a>, <a href="http://mathworld.wolfram.com/CoinTossing.html">Coin Tossing</a>.

%H <a href="/index/Aa#AHSL">Index entries for sequences of form a(n+1)=a(n)^2 + ...</a>

%F a(n+1) = (a(n))^2.

%F 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

%F a(n) = A000079(A000079(n)). - _Robert Israel_, Jan 15 2015

%F Sum_{n>=0} 1/a(n) = A007404. - _Amiram Eldar_, Oct 14 2020

%F From _Amiram Eldar_, Jan 28 2021: (Start)

%F Product_{n>=0} (1 + 1/a(n)) = 2.

%F Product_{n>=0} (1 - 1/a(n)) = A215016. (End)

%p A001146:=n->2^(2^n): seq(A001146(n), n=0..9); # _Wesley Ivan Hurt_, Sep 19 2014

%t 2^2^Range[0,10] (* _Harvey P. Dale_, Jul 20 2011 *)

%o (Magma) [2^(2^n): n in [0..8]]; // _Vincenzo Librandi_, Jun 20 2011

%o (PARI) a(n)=1<<2^n \\ _Charles R Greathouse IV_, Jul 25 2011

%o (PARI) a(n)=2^2^n \\ _Charles R Greathouse IV_, Oct 03 2012

%o (Haskell)

%o a001146 = (2 ^) . (2 ^)

%o a001146_list = iterate (^ 2) 2  -- _Reinhard Zumkeller_, Jun 04 2012

%o (Python)

%o def A001146(n): return 1<<(1<<n) # _Chai Wah Wu_, Mar 14 2023

%Y Cf. A000079, A000215, A007404, A026477, A062090, A062091, A112535, A155538, A215016.

%Y Cf. also A003018, A051179, A173419, A165420, A247165, A247219.

%K nonn,easy,nice

%O 0,1

%A _N. J. A. Sloane_