Search: a100016 -id:a100016
|
|
A007018
|
|
a(n) = a(n-1)^2 + a(n-1), a(0)=1.
(Formerly M1713)
|
|
+10
45
|
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Number of ordered trees having nodes of outdegree 0,1,2 and such that all leaves are at level n. Example: a(2)=6 because, denoting by I a path of length 2 and by Y a Y-shaped tree with 3 edges, we have I, Y, I*I, I*Y, Y*I, Y*Y, where * denotes identification of the roots. - Emeric Deutsch, Oct 31 2002
Equivalently, the number of acyclic digraphs (dags) that unravel to a perfect binary tree of height n. - Nachum Dershowitz, Jul 03 2022
a(n) has at least n different prime factors. [Saidak]
Curtiss shows that if the reciprocal sum of the multiset S = {x_1, x_2, ..., x_n} is 1, then max(S) <= a(n). - Charles R Greathouse IV, Feb 28 2007
The number of reduced ZBDDs for Boolean functions of n variables in which there is no zero sink. (ZBDDs are "zero-suppressed binary decision diagrams.") For example, a(2)=6 because of the 2-variable functions whose truth tables are 1000, 1010, 1011, 1100, 1110, 1111. - Don Knuth, Jun 04 2007
Using the methods of Aho and Sloane, Fibonacci Quarterly 11 (1973), 429-437, it is easy to show that a(n) is the integer just a tiny bit below the real number theta^{2^n}-1/2, where theta =~ 1.597910218 is the exponential of the rapidly convergent series Sum_{n>=0} log(1+1/a_n)/2^{n+1}. For example, theta^32 - 1/2 =~ 3263442.0000000383. - Don Knuth, Jun 04 2007 [Corrected by Darryl K. Nester, Jun 19 2017]
Urquhart shows that a(n) is the minimum size of a tableau refutation of the clauses of the complete binary tree of depth n, see pp. 432-434. - Charles R Greathouse IV, Jan 04 2013
For any positive a(0), the sequence a(n) = a(n-1) * (a(n-1) + 1) gives a constructive proof that there exists integers with at least n distinct prime factors, e.g. a(n). As a corollary, this gives a constructive proof of Euclid's theorem stating that there are an infinity of primes. - Daniel Forgues, Mar 03 2017
Lower bound for A100016 (with equality for the first 5 terms), where a(n)+1 is replaced by nextprime(a(n)). - M. F. Hasler, May 20 2019
|
|
REFERENCES
|
R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 94.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
Arvind Ayyer, Anne Schilling, Benjamin Steinberg and Nicolas M. Thiéry, Markov chains, R-trivial monoids and representation theory, Int. J. Algebra Comput., Vol. 25 (2015), pp. 169-231, arXiv preprint, arXiv:1401.4250 [math.CO], 2014.
|
|
FORMULA
|
a(n) = floor(c^(2^n)) where c = A077125 = 1.597910218031873178338070118157... - Benoit Cloitre, Nov 06 2002
a(1)=1, a(n) = Product_{k=1..n-1} (a(k)+1). - Benoit Cloitre, Sep 13 2003
|
|
MAPLE
|
option remember;
local aprev;
if n = 0 then
1;
else
aprev := procname(n-1) ;
aprev*(aprev+1) ;
end if;
|
|
MATHEMATICA
|
|
|
PROG
|
(PARI) a(n)=if(n>1, a(n-1)+a(n-1)^2, n) \\ Edited by M. F. Hasler, May 20 2019
(Maxima)
a[1]:1$
a[n]:=(a[n-1] + (a[n-1]^2))$
(Haskell)
a007018 n = a007018_list !! n
(Magma) [n eq 1 select 1 else Self(n-1)^2 + Self(n-1): n in [1..10]]; // Vincenzo Librandi, May 19 2015
(Python)
from itertools import islice
def A007018_gen(): # generator of terms
a = 1
while True:
yield a
a *= a+1
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A014117
|
|
Numbers n such that m^(n+1) == m (mod n) holds for all m.
|
|
+10
43
|
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
"Somebody incorrectly remembered Fermat's little theorem as saying that the congruence a^{n+1} = a (mod n) holds for all a if n is prime" (Zagier). The sequence gives the set of integers n for which this property is in fact true.
If i == j (mod n), then m^i == m^j (mod n) for all m. The latter congruence generally holds for any (m, n)=1 with i == j (mod k), k being the order of m modulo n, i.e., the least power k for which m^k == 1 (mod n). - Lekraj Beedassy, Jul 04 2002
Also, numbers n such that n divides denominator of the n-th Bernoulli number B(n) (cf. A106741). Also, numbers n such that 1^n + 2^n + 3^n + ... + n^n == 1 (mod n). Equivalently, numbers n such that B(n)*n == 1 (mod n). Equivalently, Sum_{prime p, (p-1) divides n} n/p == -1 (mod n). It is easy to see that for n > 1, n must be an even squarefree number. Moreover, the set P of prime divisors of all such n satisfies the property: if p is in P, then p-1 is the product of distinct elements of P. This set is P = {2, 3, 7, 43}, implying that the sequence is finite and complete. - Max Alekseyev, Aug 25 2013
In 2005, B. C. Kellner proved E. W. Weisstein's conjecture that denom(B_n) = n only if n = 1806. - Jonathan Sondow, Oct 14 2013
Squarefree numbers n such that b^n == 1 (mod n^2) for every b coprime to n. Squarefree terms of A341858. - Thomas Ordowski, Aug 05 2024
|
|
LINKS
|
M. A. Alekseyev, J. M. Grau, and A. M. Oller-Marcen. Computing solutions to the congruence 1^n + 2^n + ... + n^n == p (mod n). Discrete Applied Mathematics, 2018. doi:10.1016/j.dam.2018.05.022 arXiv:1602.02407 [math.NT], 2016-2018.
|
|
FORMULA
|
For n <= 5, a(n) = a(n-1)^2 + a(n-1) with a(0) = 1. - Raphie Frank, Nov 12 2012
|
|
MATHEMATICA
|
r[n_] := Reduce[ Mod[m^(n+1) - m, n] == 0, m, Integers]; ok[n_] := Range[n]-1 === Simplify[ Mod[ Flatten[ m /. {ToRules[ r[n][[2]] ]}], n], Element[C[1], Integers]]; ok[1] = True; A014117 = {}; Do[ If[ok[n], Print[n]; AppendTo[ A014117, n] ], {n, 1, 2000}] (* Jean-François Alcover, Dec 21 2011 *)
Select[Range@ 2000, Function[n, Times @@ Boole@ Map[Function[m, PowerMod[m, n + 1, n] == Mod[m, n]], Range@ n] > 0]] (* Michael De Vlieger, Dec 30 2016 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,fini,full,nice,changed
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.012 seconds
|