Search: briggs
|
| |
|
|
A000081
|
|
Number of unlabeled rooted trees with n nodes (or connected functions with a fixed point).
(Formerly M1180 N0454)
|
|
+10
689
|
|
|
|
0, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847, 1721159, 4688676, 12826228, 35221832, 97055181, 268282855, 743724984, 2067174645, 5759636510, 16083734329, 45007066269, 126186554308, 354426847597, 997171512998
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
Also, number of ways of arranging n-1 nonoverlapping circles: e.g., there are 4 ways to arrange 3 circles, as represented by ((O)), (OO), (O)O, OOO, also see example. (Of course the rules here are different from the usual counting parentheses problems - compare A000108, A001190, A001699.) See Sloane's link for a proof and Vogeler's link for illustration of a(7) as arrangement of 6 circles.
Take a string of n x's and insert n-1 ^'s and n-1 pairs of parentheses in all possible legal ways (cf. A003018). Sequence gives number of distinct functions. The single node tree is "x". Making a node f2 a child of f1 represents f1^f2. Since (f1^f2)^f3 is just f1^(f2*f3) we can think of it as f1 raised to both f2 and f3, that is, f1 with f2 and f3 as children. E.g., for n=4 the distinct functions are ((x^x)^x)^x; (x^(x^x))^x; x^((x^x)^x); x^(x^(x^x)). - W. Edwin Clark and Russ Cox Apr 29, 2003; corrected by _Keith Briggs_, Nov 14 2005
Also, number of connected multigraphs of order n without cycles except for one loop. - Washington Bomfim, Sep 04 2010
Also, number of planted trees with n+1 nodes.
Also called "Polya trees" by Genitrini (2016). - N. J. A. Sloane, Mar 24 2017
|
|
|
REFERENCES
|
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 279.
N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, pp. 42, 49.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 305, 998.
A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 451).
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 526.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 54 and 244.
Alexander S. Karpenko, Łukasiewicz Logics and Prime Numbers, Luniver Press, Beckington, 2006, p. 82.
D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3d Ed. 1997, pp. 386-388.
D. E. Knuth, The Art of Computer Programming, vol. 1, 3rd ed., Fundamental Algorithms, p. 395, ex. 2.
D. E. Knuth, TAOCP, Vol. 4, Section 7.2.1.6.
G. Polya and R. C. Read, Combinatorial Enumeration of Groups, Graphs and Chemical Compounds, Springer-Verlag, 1987, p. 63.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998. [Comment from Neven Juric: Page 64 incorrectly gives a(21)=35224832.]
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 138.
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
|
F. Harary and R. W. Robinson, The number of achiral trees, Jnl. Reine Angewandte Mathematik 278 (1975), 322-335. (Annotated scanned copy)
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Roger Vogeler, Six Circles, 2015 (illustration for a(7) as the number of arrangements of six circles).
|
|
|
FORMULA
|
G.f. A(x) satisfies A(x) = x*exp(A(x)+A(x^2)/2+A(x^3)/3+A(x^4)/4+...) [Polya]
Also A(x) = Sum_{n>=1} a(n)*x^n = x / Product_{n>=1} (1-x^n)^a(n).
Recurrence: a(n+1) = (1/n) * Sum_{k=1..n} ( Sum_{d|k} d*a(d) ) * a(n-k+1).
Asymptotically c * d^n * n^(-3/2), where c = A187770 = 0.439924... and d = A051491 = 2.955765... [Polya; Knuth, section 7.2.1.6].
Euler transform is sequence itself with offset -1. - Michael Somos, Dec 16 2001
|
|
|
EXAMPLE
|
G.f. = x + x^2 + 2*x^3 + 4*x^4 + 9*x^5 + 20*x^6 + 48*x^7 + 115*x^8 + ...
The a(6) = 20 trees with 6 nodes have the following level sequences (with level of root = 0) and parenthesis words:
01: [ 0 1 2 3 4 5 ] (((((())))))
02: [ 0 1 2 3 4 4 ] ((((()()))))
03: [ 0 1 2 3 4 3 ] ((((())())))
04: [ 0 1 2 3 4 2 ] ((((()))()))
05: [ 0 1 2 3 4 1 ] ((((())))())
06: [ 0 1 2 3 3 3 ] (((()()())))
07: [ 0 1 2 3 3 2 ] (((()())()))
08: [ 0 1 2 3 3 1 ] (((()()))())
09: [ 0 1 2 3 2 3 ] (((())(())))
10: [ 0 1 2 3 2 2 ] (((())()()))
11: [ 0 1 2 3 2 1 ] (((())())())
12: [ 0 1 2 3 1 2 ] (((()))(()))
13: [ 0 1 2 3 1 1 ] (((()))()())
14: [ 0 1 2 2 2 2 ] ((()()()()))
15: [ 0 1 2 2 2 1 ] ((()()())())
16: [ 0 1 2 2 1 2 ] ((()())(()))
17: [ 0 1 2 2 1 1 ] ((()())()())
18: [ 0 1 2 1 2 1 ] ((())(())())
19: [ 0 1 2 1 1 1 ] ((())()()())
20: [ 0 1 1 1 1 1 ] (()()()()())
(End)
|
|
|
MAPLE
|
N := 30: a := [1, 1]; for n from 3 to N do x*mul( (1-x^i)^(-a[i]), i=1..n-1); series(%, x, n+1); b := coeff(%, x, n); a := [op(a), b]; od: a; A000081 := proc(n) if n=0 then 1 else a[n]; fi; end; G000081 := series(add(a[i]*x^i, i=1..N), x, N+2); # also used in A000055
spec := [ T, {T=Prod(Z, Set(T))} ]; A000081 := n-> combstruct[count](spec, size=n); [seq(combstruct[count](spec, size=n), n=0..40)];
# a much more efficient method for computing the result with Maple. It uses two procedures:
a := proc(n) local k; a(n) := add(k*a(k)*s(n-1, k), k=1..n-1)/(n-1) end proc:
a(0) := 0: a(1) := 1: s := proc(n, k) local j; s(n, k) := add(a(n+1-j*k), j=1..iquo(n, k)); # Joe Riel (joer(AT)san.rr.com), Jun 23 2008
# even more efficient, uses the Euler transform:
with(numtheory): a:= proc(n) option remember; local d, j; `if`(n<=1, n, (add(add(d*a(d), d=divisors(j)) *a(n-j), j=1..n-1))/ (n-1)) end:
|
|
|
MATHEMATICA
|
s[ n_, k_ ] := s[ n, k ]=a[ n+1-k ]+If[ n<2k, 0, s[ n-k, k ] ]; a[ 1 ]=1; a[ n_ ] := a[ n ]=Sum[ a[ i ]s[ n-1, i ]i, {i, 1, n-1} ]/(n-1); Table[ a[ i ], {i, 1, 30} ] (* Robert A. Russell *)
a[n_] := a[n] = If[n <= 1, n, Sum[Sum[d*a[d], {d, Divisors[j]}]*a[n-j], {j, 1, n-1}]/(n-1)]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 17 2014, after Alois P. Heinz *)
a[n_] := a[n] = If[n <= 1, n, Sum[a[n - j] DivisorSum[j, # a[#] &], {j, n - 1}]/(n - 1)]; Table[a[n], {n, 0, 30}] (* Jan Mangaldan, May 07 2014, after Alois P. Heinz *)
(* first do *) << NumericalDifferentialEquationAnalysis`; (* then *)
a[n:0|1] := n; a[n_] := a[n] = Sum[m a[m] a[n-k*m], {m, n-1}, {k, (n-1)/m}]/(n-1); Table[a[n], {n, 0, 30}] (* Vladimir Reshetnikov, Nov 06 2015 *)
terms = 31; A[_] = 0; Do[A[x_] = x*Exp[Sum[A[x^k]/k, {k, 1, j}]] + O[x]^j // Normal, {j, 1, terms}]; CoefficientList[A[x], x] (* Jean-François Alcover, Jan 11 2018 *)
|
|
|
PROG
|
(PARI) {a(n) = local(A = x); if( n<1, 0, for( k=1, n-1, A /= (1 - x^k + x * O(x^n))^polcoeff(A, k)); polcoeff(A, n))}; /* Michael Somos, Dec 16 2002 */
(PARI) {a(n) = local(A, A1, an, i); if( n<1, 0, an = Vec(A = A1 = 1 + O(x^n)); for( m=2, n, i=m\2; an[m] = sum( k=1, i, an[k] * an[m-k]) + polcoeff( if( m%2, A *= (A1 - x^i)^-an[i], A), m-1)); an[n])}; /* Michael Somos, Sep 05 2003 */
(PARI) N=66; A=vector(N+1, j, 1);
for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) );
(Magma) N := 30; P<x> := PowerSeriesRing(Rationals(), N+1); f := func< A | x*&*[Exp(Evaluate(A, x^k)/k) : k in [1..N]]>; G := x; for i in [1..N] do G := f(G); end for; G000081 := G; A000081 := [0] cat Eltseq(G); // Geoff Bailey (geoff(AT)maths.usyd.edu.au), Nov 30 2009
(Maxima)
g(m):= block([si, v], s:0, v:divisors(m), for si in v do (s:s+r(m/si)/si), s);
r(n):=if n=1 then 1 else sum(Co(n-1, k)/k!, k, 1, n-1);
Co(n, k):=if k=1 then g(n) else sum(g(i+1)*Co(n-i-1, k-1), i, 0, n-k);
(Haskell)
import Data.List (genericIndex)
a000081 = genericIndex a000081_list
a000081_list = 0 : 1 : f 1 [1, 0] where
f x ys = y : f (x + 1) (y : ys) where
y = sum (zipWith (*) (map h [1..x]) ys) `div` x
h = sum . map (\d -> d * a000081 d) . a027750_row
(Sage)
@CachedFunction
def a(n):
if n < 2: return n
return add(add(d*a(d) for d in divisors(j))*a(n-j) for j in (1..n-1))/(n-1)
(Sage) [0]+[RootedTrees(n).cardinality() for n in range(1, 31)] # Freddy Barrera, Apr 07 2019
(Python)
from functools import lru_cache
from sympy import divisors
@lru_cache(maxsize=None)
def divisor_tuple(n): # cached unordered tuple of divisors
return tuple(divisors(n, generator=True))
@lru_cache(maxsize=None)
|
|
|
CROSSREFS
|
Cf. A000041 (partitions), A000055 (unrooted trees), A000169, A001858, A005200, A027750, A051491, A051492, A093637, A187770, A199812, A255170, A087803 (partial sums).
|
|
|
KEYWORD
|
nonn,easy,core,nice,eigen
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000124
|
|
Central polygonal numbers (the Lazy Caterer's sequence): n(n+1)/2 + 1; or, maximal number of pieces formed when slicing a pancake with n cuts.
(Formerly M1041 N0391)
|
|
+10
425
|
|
|
|
1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, 232, 254, 277, 301, 326, 352, 379, 407, 436, 466, 497, 529, 562, 596, 631, 667, 704, 742, 781, 821, 862, 904, 947, 991, 1036, 1082, 1129, 1177, 1226, 1276, 1327, 1379
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
These are Hogben's central polygonal numbers with the (two-dimensional) symbol
2
.P
1 n
The first line cuts the pancake into 2 pieces. For n > 1, the n-th line crosses every earlier line (avoids parallelism) and also avoids every previous line intersection, thus increasing the number of pieces by n. For 16 lines, for example, the number of pieces is 2 + 2 + 3 + 4 + 5 + ... + 16 = 137. These are the triangular numbers plus 1 (cf. A000217).
m = (n-1)(n-2)/2 + 1 is also the smallest number of edges such that all graphs with n nodes and m edges are connected. - _Keith Briggs_, May 14 2004
Also maximal number of grandchildren of a binary vector of length n+2. E.g., a binary vector of length 6 can produce at most 11 different vectors when 2 bits are deleted.
This is also the order dimension of the (strong) Bruhat order on the finite Coxeter group B_{n+1}. - Nathan Reading (reading(AT)math.umn.edu), Mar 07 2002
Number of 132- and 321-avoiding permutations of {1,2,...,n+1}. - Emeric Deutsch, Mar 14 2002
For n >= 1 a(n) is the number of terms in the expansion of (x+y)*(x^2+y^2)*(x^3+y^3)*...*(x^n+y^n). - Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 28 2003
Also the number of terms in (1)(x+1)(x^2+x+1)...(x^n+...+x+1); see A000140.
Narayana transform (analog of the binomial transform) of vector [1, 1, 0, 0, 0, ...] = A000124; using the infinite lower Narayana triangle of A001263 (as a matrix), N; then N * [1, 1, 0, 0, 0, ...] = A000124. - Gary W. Adamson, Apr 28 2005
Number of interval subsets of {1, 2, 3, ..., n} (cf. A002662). - Jose Luis Arregui (arregui(AT)unizar.es), Jun 27 2006
Define a number of straight lines in the plane to be in general arrangement when (1) no two lines are parallel, (2) there is no point common to three lines. Then these are the maximal numbers of regions defined by n straight lines in general arrangement in the plane. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
Note that a(n) = a(n-1) + A000027(n-1). This has the following geometrical interpretation: Suppose there are already n-1 lines in general arrangement, thus defining the maximal number of regions in the plane obtainable by n-1 lines and now one more line is added in general arrangement. Then it will cut each of the n-1 lines and acquire intersection points which are in general arrangement. (See the comments on A000027 for general arrangement with points.) These points on the new line define the maximal number of regions in 1-space definable by n-1 points, hence this is A000027(n-1), where for A000027 an offset of 0 is assumed, that is, A000027(n-1) = (n+1)-1 = n. Each of these regions acts as a dividing wall, thereby creating as many new regions in addition to the a(n-1) regions already there, hence a(n) = a(n-1) + A000027(n-1). Cf. the comments on A000125 for an analogous interpretation. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
When constructing a zonohedron, one zone at a time, out of (up to) 3-d non-intersecting parallelepipeds, the n-th element of this sequence is the number of edges in the n-th zone added with the n-th "layer" of parallelepipeds. (Verified up to 10-zone zonohedron, the enneacontahedron.) E.g., adding the 10th zone to the enneacontahedron requires 46 parallel edges (edges in the 10th zone) by looking directly at a 5-valence vertex and counting visible vertices. - Shel Kaphan, Feb 16 2006
Binomial transform of (1, 1, 1, 0, 0, 0, ...) and inverse binomial transform of A072863: (1, 3, 9, 26, 72, 192, ...). - Gary W. Adamson, Oct 15 2007
If Y is a 2-subset of an n-set X then, for n >= 3, a(n-3) is the number of (n-2)-subsets of X which do not have exactly one element in common with Y. - Milan Janjic, Dec 28 2007
It appears that a(n) is the number of distinct values among the fractions F(i+1)/F(j+1) as j ranges from 1 to n and, for each fixed j, i ranges from 1 to j, where F(i) denotes the i-th Fibonacci number. - John W. Layman, Dec 02 2008
a(n) is the number of subsets of {1,2,...,n} that contain at most two elements. - Geoffrey Critzer, Mar 10 2009
For n >= 2, a(n) gives the number of sets of subsets A_1, A_2, ..., A_n of n = {1, 2, ..., n} such that Meet_{i = 1..n} A_i is empty and Sum_{j in [n]} (|Meet{i = 1..n, i != j} A_i|) is a maximum. - Srikanth K S, Oct 22 2009
The numbers along the left edge of Floyd's triangle. - Paul Muljadi, Jan 25 2010
Let A be the Hessenberg matrix of order n, defined by: A[1,j] = A[i,i]:=1, A[i,i-1] = -1, and A[i,j] = 0 otherwise. Then, for n >= 1, a(n-1) = (-1)^(n-1)*coeff(charpoly(A,x),x). - Milan Janjic, Jan 24 2010
Also the number of deck entries of Euler's ship. See the Meijer-Nepveu link. - Johannes W. Meijer, Jun 21 2010
(1 + x^2 + x^3 + x^4 + x^5 + ...)*(1 + 2x + 3x^2 + 4x^3 + 5x^4 + ...) = (1 + 2x + 4x^2 + 7x^3 + 11x^4 + ...). - Gary W. Adamson, Jul 27 2010
The number of length n binary words that have no 0-digits between any pair of consecutive 1-digits. - Jeffrey Liese, Dec 23 2010
Let b(0) = b(1) = 1; b(n) = max(b(n-1)+n-1, b(n-2)+n-2) then a(n) = b(n+1). - Yalcin Aktar, Jul 28 2011
Also number of distinct sums of 1 through n where each of those can be + or -. E.g., {1+2,1-2,-1+2,-1-2} = {3,-1,1,-3} and a(2) = 4. - Toby Gottfried, Nov 17 2011
This sequence is complete because the sum of the first n terms is always greater than or equal to a(n+1)-1. Consequently, any nonnegative number can be written as a sum of distinct terms of this sequence. See A204009, A072638. - Frank M Jackson, Jan 09 2012
The sequence is the number of distinct sums of subsets of the nonnegative integers, and its first differences are the positive integers. See A208531 for similar results for the squares. - John W. Layman, Feb 28 2012
Apparently the number of Dyck paths of semilength n+1 in which the sum of the first and second ascents add to n+1. - David Scambler, Apr 22 2013
Without 1 and 2, a(n) equals the terminus of the n-th partial sum of sequence 1, 1, 2. Explanation: 1st partial sums of 1, 1, 2 are 1, 2, 4; 2nd partial sums are 1, 3, 7; 3rd partial sums are 1, 4, 11; 4th partial sums are 1, 5, 16, etc. - Bob Selcoe, Jul 04 2013
Equivalently, numbers of the form 2*m^2+m+1, where m = 0, -1, 1, -2, 2, -3, 3, ... . - Bruno Berselli, Apr 08 2014
For n >= 2: quasi-triangular numbers; the almost-triangular numbers being A000096(n), n >= 2. Note that 2 is simultaneously almost-triangular and quasi-triangular. - Daniel Forgues, Apr 21 2015
n points in general position determine "n choose 2" lines, so A055503(n) <= a(n(n-1)/2). If n > 3, the lines are not in general position and so A055503(n) < a(n(n-1)/2). - Jonathan Sondow, Dec 01 2015
The digital root is period 9 (1, 2, 4, 7, 2, 7, 4, 2, 1), also the digital roots of centered 10-gonal numbers (A062786), for n > 0, A133292. - Peter M. Chema, Sep 15 2016
For n >= 0, a(n) is the number of weakly unimodal sequences of length n over the alphabet {1, 2}. - Armend Shabani, Mar 10 2017
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) < e(j) != e(k). [Martinez and Savage, 2.4]
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) < e(j) and e(i) < e(k). [Martinez and Savage, 2.4]
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) != e(k). [Martinez and Savage, 2.4]
(End)
The odd prime factors != 7 occur in an interval of p successive terms either never or exactly twice, while 7 always occurs only once. If a prime factor p appears in a(n) and a(m) within such an interval, then n + m == -1 (mod p). When 7 divides a(n), then 2*n == -1 (mod 7). a(n) is never divisible by the prime numbers given in A003625.
While all prime factors p != 7 can occur to any power, a(n) is never divisible by 7^2. The prime factors are given in A045373. The prime terms of this sequence are given in A055469.
(End)
a(n-1) is the greatest sum of arch lengths for the top arches of a semi-meander with n arches. An arch length is the number of arches covered + 1.
/\ The top arch has a length of 3. /\ The top arch has a length of 3.
/ \ Both bottom arches have a //\\ The middle arch has a length of 2.
//\/\\ length of 1. ///\\\ The bottom arch has a length of 1.
Example: for n = 4, a(4-1) = a(3) = 7 /\
//\\
/\ ///\\\ 1 + 3 + 2 + 1 = 7. (End)
a(n+1) is the a(n)-th smallest positive integer that has not yet appeared in the sequence. - Matthew Malone, Aug 26 2021
For n> 0, let the n-dimensional cube {0,1}^n be, provided with the Hamming distance, d. Given an element x in {0,1}^n, a(n) is the number of elements y in {0,1}^n such that d(x, y) <= 2. Example: n = 4. (0,0,0,0), (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1), (0,0,1,1), (0,1,0,1), (0,1,1,0), (1,0,0,1), (1,0,1,0), (1,1,0,0) are at distance <= 2 from (0,0,0,0), so a(4) = 11. - Yosu Yurramendi, Dec 10 2021
a(n) is the sum of the first three entries of row n of Pascal's triangle. - Daniel T. Martin, Apr 13 2022
a(n-1) is the number of Grassmannian permutations that avoid a pattern, sigma, where sigma is a pattern of size 3 with exactly one descent. For example, sigma is one of the patterns, {132, 213, 231, 312}. - Jessica A. Tomasko, Sep 14 2022
|
|
|
REFERENCES
|
Robert B. Banks, Slicing Pizzas, Racing Turtles and Further Adventures in Applied Mathematics, Princeton Univ. Press, 1999. See p. 24.
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 72, Problem 2.
Henry Ernest Dudeney, Amusements in Mathematics, Nelson, London, 1917, page 177.
Derrick Niederman, Number Freak, From 1 to 200 The Hidden Language of Numbers Revealed, A Perigee Book, NY, 2009, p. 83.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
Alain M. Robert, A Course in p-adic Analysis, Springer-Verlag, 2000; p. 213.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane, On single-deletion-correcting codes, in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
William Allen Whitworth, DCC Exercises in Choice and Chance, Stechert, NY, 1945, p. 30.
Akiva M. Yaglom and Isaak M. Yaglom, Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. New York: Dover Publications, Inc., 1987, p. 13, #44 (First published: San Francisco: Holden-Day, Inc., 1964).
|
|
|
LINKS
|
M. F. Hasler, Interactive illustration of A000124. [Sep 06 2017: The user can choose the slices to make, but the program can suggest a set of n slices which should yield the maximum number of pieces. For n slices this obviously requires 2n endpoints, or 2n+1 if they are equally spaced, so if there are not enough "blobs", their number is accordingly increased. This is the distinction between "draw" (done when you change the slices or number of blobs by hand) and "suggest" (propose a new set of slices).]
Rodica Simion and Frank W. Schmidt, Restricted permutations, European J. Combin., 6, 383-406, 1985; see Example 3.5.
|
|
|
FORMULA
|
G.f.: (1 - x + x^2)/(1 - x)^3. Simon Plouffe in his 1992 dissertation
G.f.: (1 - x^6)/((1 - x)^2*(1 - x^2)*(1 - x^3)). a(n) = a(-1 - n) for all n in Z. - Michael Somos, Sep 04 2006
Euler transform of length 6 sequence [ 2, 1, 1, 0, 0, -1]. - Michael Somos, Sep 04 2006
a(n+3) = 3*a(n+2) - 3*a(n+1) + a(n) and a(1) = 1, a(2) = 2, a(3) = 4. - Artur Jasinski, Oct 21 2008
a(n) = a(n-1) + n. E.g.f.:(1 + x + x^2/2)*exp(x). - Geoffrey Critzer, Mar 10 2009
a(n) = Sum_{k = 0..n + 1} binomial(n+1, 2(k - n)). - Paul Barry, Aug 29 2004
a(n) = binomial(n+2, 1) - 2*binomial(n+1, 1) + binomial(n+2, 2). - Zerinvary Lajos, May 12 2006
a(n) = Sum_{l_1 = 0..n + 1} Sum_{l_2 = 0..n}...Sum_{l_i = 0..n - i}...Sum_{l_n = 0..1} delta(l_1, l_2, ..., l_i, ..., l_n) where delta(l_1, l_2, ..., l_i, ..., l_n) = 0 if any l_i != l_(i+1) and l_(i+1) != 0 and delta(l_1, l_2, ..., l_i, ..., l_n) = 1 otherwise. (End)
a(n) = 2*a(n-1) - a(n-2) + 1. - Eric Werley, Jun 27 2011
E.g.f.: exp(x)*(1+x+(x^2)/2) = Q(0); Q(k) = 1+x/(1-x/(2+x-4/(2+x*(k+1)/Q(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Nov 21 2011
Dirichlet g.f.: (zeta(s-2) + zeta(s-1) + 2*zeta(s))/2.
Sum_{n >= 0} 1/a(n) = 2*Pi*tanh(sqrt(7)*Pi/2)/sqrt(7) = A226985. (End)
a(n) = 2*a(n-1) - binomial(n-1, 2) and a(0) = 1. - Armend Shabani, Mar 10 2017
a(n) = (Sum_{i=n-2..n+2} A000217(i))/5.
a(n) = (Sum_{i=n-2..n+2} A002378(i))/10.
a(n) = (Sum_{i=n..n+2} A002061(i)+1)/6.
a(n) = (Sum_{i=n-1..n+2} A000290(i)+2)/8.
(End)
Product_{n>=0} (1 + 1/a(n)) = cosh(sqrt(15)*Pi/2)*sech(sqrt(7)*Pi/2).
Product_{n>=1} (1 - 1/a(n)) = 2*Pi*sech(sqrt(7)*Pi/2). (End)
a((n^2-3n+6)/2) + a((n^2-n+4)/2) = a(n^2-2n+6)/2. - Charlie Marion, Feb 14 2023
|
|
|
EXAMPLE
|
a(3) = 7 because the 132- and 321-avoiding permutations of {1, 2, 3, 4} are 1234, 2134, 3124, 2314, 4123, 3412, 2341.
G.f. = 1 + 2*x + 4*x^2 + 7*x^3 + 11*x^4 + 16*x^5 + 22*x^6 + 29*x^7 + ...
|
|
|
MAPLE
|
|
|
|
MATHEMATICA
|
Table[PolygonalNumber[n] + 1, {n, 0, 52}] (* Michael De Vlieger, Jun 30 2016, Version 10.4 *)
|
|
|
PROG
|
(PARI) {a(n) = (n^2 + n) / 2 + 1}; /* Michael Somos, Sep 04 2006 */
(Haskell)
a000124 = (+ 1) . a000217
(Python)
def a(n): return n*(n+1)//2 + 1
|
|
|
CROSSREFS
|
Cf. A000096 (Maximal number of pieces that can be obtained by cutting an annulus with n cuts, for n >= 1).
Cf. A002061, A002522, A016028, A055503, A072863, A144328, A177862, A263883, A000127, A005408, A006261, A016813, A058331, A080856, A086514, A161701, A161702, A161703, A161704, A161706, A161707, A161708, A161710, A161711, A161712, A161713, A161715, A051601, A228918.
Cf. A055469 Quasi-triangular primes.
|
|
|
KEYWORD
|
nonn,core,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000959
|
|
Lucky numbers.
(Formerly M2616 N1035)
|
|
+10
304
|
|
|
|
1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 99, 105, 111, 115, 127, 129, 133, 135, 141, 151, 159, 163, 169, 171, 189, 193, 195, 201, 205, 211, 219, 223, 231, 235, 237, 241, 259, 261, 267, 273, 283, 285, 289, 297, 303
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
An interesting general discussion of the phenomenon of 'random primes' (generalizing the lucky numbers) occurs in Hawkins (1958). Heyde (1978) proves that Hawkins' random primes do not only almost always satisfy the Prime Number Theorem but also the Riemann Hypothesis. - Alf van der Poorten, Jun 27 2002
Bui and Keating establish an asymptotic formula for the number of k-difference twin primes, and more generally to all l-tuples, of Hawkins primes, a probabilistic model of the Eratosthenes sieve. The formula for k = 1 was obtained by Wunderlich [Acta Arith. 26 (1974), 59 - 81]. - Jonathan Vos Post, Mar 24 2009. (This is quoted from the abstract of the Bui-Keating (2006) article, Joerg Arndt, Jan 04 2014)
It appears that a 1's line is formed, as in the Gilbreath's conjecture, if we use 2 (or 4), 3, 5 (differ of 7), 9, 13, 15, 21, 25, ... instead of A000959 1, 3, 7, 9, 13, 15, 21, 25, ... - Eric Desbiaux, Mar 25 2010
|
|
|
REFERENCES
|
Martin Gardner, Gardner's Workout, Chapter 21 "Lucky Numbers and 2187" pp. 149-156 A. K. Peters MA 2002.
Richard K. Guy, Unsolved Problems in Number Theory, C3.
C. S. Ogilvy, Tomorrow's Math. 2nd ed., Oxford Univ. Press, 1972, p. 99.
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).
M. L. Stein and P. R. Stein, Tables of the Number of Binary Decompositions of All Even Numbers Less Than 200,000 into Prime Numbers and Lucky Numbers. Report LA-3106, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Sep 1964.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, 114.
|
|
|
LINKS
|
Popular Computing (Calabasas, CA), Sieves: Problem 43, Vol. 2 (No. 13, Apr 1974), pp. 6-7. This is Sieve #7. [Annotated and scanned copy]
|
|
|
FORMULA
|
Start with the natural numbers. Delete every 2nd number, leaving 1 3 5 7 ...; the 2nd number remaining is 3, so delete every 3rd number, leaving 1 3 7 9 13 15 ...; now delete every 7th number, leaving 1 3 7 9 13 ...; now delete every 9th number; etc.
a(n) = A258207(n,n). [Where A258207 is a square array constructed from the numbers remaining after each step described above.] - Antti Karttunen, Aug 06 2015
(End)
|
|
|
MAPLE
|
## luckynumbers(n) returns all lucky numbers from 1 to n. ## Try n=10^5 just for fun. luckynumbers:=proc(n) local k, Lnext, Lprev; Lprev:=[$1..n]; for k from 1 do if k=1 or k=2 then Lnext:= map(w-> Lprev[w], remove(z -> z mod Lprev[2] = 0, [$1..nops(Lprev)])); if nops(Lnext)=nops(Lprev) then break fi; Lprev:=Lnext; else Lnext:= map(w-> Lprev[w], remove(z -> z mod Lprev[k] = 0, [$1..nops(Lprev)])); if nops(Lnext)=nops(Lprev) then break fi; Lprev:=Lnext; fi; od; return Lnext; end: # Walter Kehowski, Jun 05 2008; typo fixed by Robert Israel, Nov 19 2014
# Alternative
A000959List := proc(mx) local L, n, r;
L:= [seq(2*i+1, i=0..mx)]:
for n from 2 while n < nops(L) do
r:= L[n];
L:= subsop(seq(r*i=NULL, i=1..nops(L)/r), L);
od: L end:
|
|
|
MATHEMATICA
|
luckies = 2*Range@200 - 1; f[n_] := Block[{k = luckies[[n]]}, luckies = Delete[luckies, Table[{k}, {k, k, Length@luckies, k}]]]; Do[f@n, {n, 2, 30}]; luckies (* Robert G. Wilson v, May 09 2006 *)
sieveMax = 10^6; luckies = Range[1, sieveMax, 2]; sieve[n_] := Module[{k = luckies[[n]]}, luckies = Delete[luckies, Table[{i}, {i, k, Length[luckies], k}]]]; n = 1; While[luckies[[n]] < Length[luckies], n++; sieve[n]]; luckies
L = Table[2*i + 1, {i, 0, 10^3}]; For[n = 2, n < Length[L], r = L[[n++]]; L = ReplacePart[L, Table[r*i -> Nothing, {i, 1, Length[L]/r}]]]; L (* Jean-François Alcover, Mar 15 2016, after Robert Israel *)
|
|
|
PROG
|
(Haskell)
a000959 n = a000959_list !! (n-1)
a000959_list = 1 : sieve 2 [1, 3..] where
sieve k xs = z : sieve (k + 1) (lucky xs) where
z = xs !! (k - 1 )
lucky ws = us ++ lucky vs where
(us, _:vs) = splitAt (z - 1) ws
(C++) // See Wilson link, Nov 14 2012
(PARI) A000959_upto(nMax)={my(v=vectorsmall(nMax\2, k, 2*k-1), i=1, q); while(v[i++]<=#v, v=vecextract(v, 2^#v-1-(q=1<<v[i])^(#v\v[i])\(q-1)<<(v[i]-1) )); v} \\ M. F. Hasler, Sep 22 2013, improved Jan 20 2020
(Python)
def lucky(n):
L = list(range(1, n + 1, 2))
j = 1
while j <= len(L) - 1 and L[j] <= len(L):
del L[L[j]-1::L[j]]
j += 1
return L
(Scheme)
(define (A000959 n) ((rowfun_n_for_A000959sieve n) n)) ;; Code for rowfun_n_for_A000959sieve given in A255543.
|
|
|
CROSSREFS
|
Cf. A145649 (characteristic function).
Cf. A109497 (works as a left inverse function).
|
|
|
KEYWORD
|
nonn,easy,nice,core,changed
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000088
|
|
Number of graphs on n unlabeled nodes.
(Formerly M1253 N0479)
|
|
+10
298
|
|
|
|
1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864, 165091172592, 50502031367952, 29054155657235488, 31426485969804308768, 64001015704527557894928, 245935864153532932683719776, 1787577725145611700547878190848, 24637809253125004524383007491432768
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Euler transform of the sequence A001349.
Also, number of equivalence classes of sign patterns of totally nonzero symmetric n X n matrices.
|
|
|
REFERENCES
|
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 430.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
Thomas Boyer-Kassem, Conor Mayo-Wilson, Scientific Collaboration and Collective Knowledge: New Essays, New York, Oxford University Press, 2018, see page 47.
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 54.
Lupanov, O. B. Asymptotic estimates of the number of graphs with n edges. (Russian) Dokl. Akad. Nauk SSSR 126 1959 498--500. MR0109796 (22 #681).
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
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
|
Natalie Arkus, Vinothan N. Manoharan and Michael P. Brenner. Deriving Finite Sphere Packings, arXiv:1011.5412 [cond-mat.soft], Nov 24, 2010. (See Table 1.)
P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp. [Annotated scanned copy]
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Overview of the 17 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
|
|
|
FORMULA
|
a(n) = 2^binomial(n, 2)/n!*(1+(n^2-n)/2^(n-1)+8*n!/(n-4)!*(3*n-7)*(3*n-9)/2^(2*n)+O(n^5/2^(5*n/2))) (see Harary, Palmer reference). - Vladeta Jovovic and Benoit Cloitre, Feb 01 2003
a(n) = 2^binomial(n, 2)/n!*[1+2*n$2*2^{-n}+8/3*n$3*(3n-7)*2^{-2n}+64/3*n$4*(4n^2-34n+75)*2^{-3n}+O(n^8*2^{-4*n})] where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1). - _Keith Briggs_, Oct 24 2005
From David Pasino (davepasino(AT)yahoo.com), Jan 31 2009: (Start)
a(n) = a(n, 2), where a(n, t) is the number of t-uniform hypergraphs on n unlabeled nodes (cf. A000665 for t = 3 and A051240 for t = 4).
a(n, t) = Sum_{c : 1*c_1+2*c_2+...+n*c_n=n} per(c)*2^f(c), where:
..per(c) = 1/(Product_{i=1..n} c_i!*i^c_i);
..f(c) = (1/ord(c)) * Sum_{r=1..ord(c)} Sum_{x : 1*x_1+2*x_2+...+t*x_t=t} Product_{k=1..t} binomial(y(r, k; c), x_k);
..ord(c) = lcm{i : c_i>0};
..y(r, k; c) = Sum_{s|r : gcd(k, r/s)=1} s*c_(k*s) is the number of k-cycles of the r-th power of a permutation of type c. (End)
a(n) ~ 2^binomial(n,2)/n! [see Flajolet and Sedgewick p. 106, Gross and Yellen, p. 519, etc.]. - N. J. A. Sloane, Nov 11 2013
For asymptotics see also Lupanov 1959, 1960, also Turner and Kautz, p. 18. - N. J. A. Sloane, Apr 08 2014
a(n) = G(1) where G(z) = (1/n!) Sum_g det(I-g z^2)/det(I-g z) and g runs through the natural matrix n X n representation of the pair group A^2_n (for A^2_n see F. Harary and E. M. Palmer, Graphical Enumeration, page 83). - Leonid Bedratyuk, May 02 2015
From _Keith Briggs_, Jun 24 2016: (Start)
a(n) = 2^binomial(n,2)/n!*(
1+
2^( -n + 1)*n$2+
2^(-2*n + 3)*n$3*(n-7/3)+
2^(-3*n + 6)*n$4*(4*n^2/3 - 34*n/3 + 25) +
2^(-4*n + 10)*n$5*(8*n^3/3 - 142*n^2/3 + 2528*n/9 - 24914/45) +
2^(-5*n + 15)*n$6*(128*n^4/15 - 2296*n^3/9 + 25604*n^2/9 - 630554*n/45 + 25704) +
2^(-6*n + 21)*n$7*(2048*n^5/45 - 18416*n^4/9 + 329288*n^3/9 - 131680816*n^2/405 + 193822388*n/135 - 7143499196/2835) + ...),
where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1), using the method of Wright 1969.
(End)
|
|
|
MAPLE
|
# To produce all graphs on 4 nodes, for example:
with(GraphTheory):
L:=[NonIsomorphicGraphs](4, output=graphs, outputform=adjacency): # N. J. A. Sloane, Oct 07 2013
seq(GraphTheory[NonIsomorphicGraphs](n, output=count), n=1..10); # Juergen Will, Jan 02 2018
# alternative Maple program:
b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(ceil((p[j]-1)/2)
+add(igcd(p[k], p[j]), k=1..j-1), j=1..nops(p)))([l[], 1$n])),
add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
end:
a:= n-> b(n$2, []):
|
|
|
MATHEMATICA
|
Needs["Combinatorica`"]
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
b[n_, i_, l_] := If[n==0 || i==1, 1/n!*2^(Function[p, Sum[Ceiling[(p[[j]]-1 )/2]+Sum[GCD[p[[k]], p[[j]]], {k, 1, j-1}], {j, 1, Length[p]}]][Join[l, Table[1, {n}]]]), Sum[b[n-i*j, i-1, Join[l, Table[i, {j}]]]/j!/i^j, {j, 0, n/i}]];
a[n_] := b[n, n, {}];
|
|
|
PROG
|
(Sage)
def a(n):
return len(list(graphs(n)))
(PARI)
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017
(Python)
from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A000088(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r, s) for r, s in combinations(p.keys(), 2))+sum((q>>1)*r+(q*r*(r-1)>>1) for q, r in p.items()), prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 02 2024
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
core,nonn,nice,changed
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Harary gives an incorrect value for a(8); compare A007149
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A002450
|
|
a(n) = (4^n - 1)/3.
(Formerly M3914 N1608)
|
|
+10
292
|
|
|
|
0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381, 349525, 1398101, 5592405, 22369621, 89478485, 357913941, 1431655765, 5726623061, 22906492245, 91625968981, 366503875925, 1466015503701, 5864062014805, 23456248059221, 93824992236885, 375299968947541
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
For n > 0, a(n) is the degree (n-1) "numbral" power of 5 (see A048888 for the definition of numbral arithmetic). Example: a(3) = 21, since the numbral square of 5 is 5(*)5 = 101(*)101(base 2) = 101 OR 10100 = 10101(base 2) = 21, where the OR is taken bitwise. - John W. Layman, Dec 18 2001
a(n) is composite for all n > 2 and has factors x, (3*x + 2*(-1)^n) where x belongs to A001045. In binary the terms greater than 0 are 1, 101, 10101, 1010101, etc. - John McNamara, Jan 16 2002
Number of n X 2 binary arrays with path of adjacent 1's from upper left corner to right column. - R. H. Hardin, Mar 16 2002
The Collatz-function iteration started at a(n), for n >= 1, will end at 1 after 2*n+1 steps. - Labos Elemer, Sep 30 2002 [corrected by Wolfdieter Lang, Aug 16 2021]
Number of walks of length 2n between two vertices at distance 2 in the cycle graph C_6. For n = 2 we have for example 5 walks of length 4 from vertex A to C: ABABC, ABCBC, ABCDC, AFABC and AFEDC. - Herbert Kociemba, May 31 2004
Also number of walks of length 2n + 1 between two vertices at distance 3 in the cycle graph C_12. - Herbert Kociemba, Jul 05 2004
a(n+1) is the number of steps that are made when generating all n-step random walks that begin in a given point P on a two-dimensional square lattice. To make one step means to mark one vertex on the lattice (compare A080674). - Pawel P. Mazur (Pawel.Mazur(AT)pwr.wroc.pl), Mar 13 2005
a(n+1) is the sum of square divisors of 4^n. - Paul Barry, Oct 13 2005
a(n+1) is the decimal number generated by the binary bits in the n-th generation of the Rule 250 elementary cellular automaton. - Eric W. Weisstein, Apr 08 2006
a(k) = [M^k]_2,1, where M is the 3 X 3 matrix defined as follows: M = [1, 1, 1; 1, 3, 1; 1, 1, 1]. - Simone Severini, Jun 11 2006
a(n-1) / a(n) = percentage of wasted storage if a single image is stored as a pyramid with a each subsequent higher resolution layer containing four times as many pixels as the previous layer. n is the number of layers. - Victor Brodsky (victorbrodsky(AT)gmail.com), Jun 15 2006
k is in the sequence if and only if C(4k + 1, k) (A052203) is odd. - Paul Barry, Mar 26 2007
This sequence also gives the number of distinct 3-colorings of the odd cycle C(2*n - 1). - _Keith Briggs_, Jun 19 2007
All numbers of the form m*4^m + (4^m-1)/3 have the property that they are sums of two squares and also their indices are the sum of two squares. This follows from the identity m*4^m + (4^m-1)/3 = 4(4(..4(4m + 1) + 1) + 1) + 1 ..) + 1. - Artur Jasinski, Nov 12 2007
For n > 0, terms are the numbers that, in base 4, are repunits: 1_4, 11_4, 111_4, 1111_4, etc. - Artur Jasinski, Sep 30 2008
Let A be the Hessenberg matrix of order n, defined by: A[1, j] = 1, A[i, i] := 5, (i > 1), A[i, i - 1] = -1, and A[i, j] = 0 otherwise. Then, for n >= 1, a(n) = charpoly(A,1). - Milan Janjic, Jan 27 2010
This is the sequence A(0, 1; 3, 4; 2) = A(0, 1; 4, 0; 1) of the family of sequences [a, b : c, d : k] considered by G. Detlefs, and treated as A(a, b; c, d; k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010
6*a(n) + 1 is every second Mersenne number greater than or equal to M3, hence all Mersenne primes greater than M2 must be a 6*a(n) + 1 of this sequence. - Roderick MacPhee, Nov 01 2010
Smallest number having alternating bit sum n. Cf. A065359.
For n = 1, 2, ..., the last digit of a(n) is 1, 5, 1, 5, ... . - Washington Bomfim, Jan 21 2011
Rule 50 elementary cellular automaton generates this sequence. This sequence also appears in the second column of array in A173588. - Paul Muljadi, Jan 27 2011
Sequence found by reading the line from 0, in the direction 0, 5, ... and the line from 1, in the direction 1, 21, ..., in the square spiral whose edges are the Jacobsthal numbers A001045 and whose vertices are the numbers A000975. These parallel lines are two semi-diagonals in the spiral. - Omar E. Pol, Sep 10 2011
a(n), n >= 1, is also the inverse of 3, denoted by 3^(-1), Modd(2^(2*n - 1)). For Modd n see a comment on A203571. E.g., a(2) = 5, 3 * 5 = 15 == 1 (Modd 8), because floor(15/8) = 1 is odd and -15 == 1 (mod 8). For n = 1 note that 3 * 1 = 3 == 1 (Modd 2) because floor(3/2) = 1 and -3 == 1 (mod 2). The inverse of 3 taken Modd 2^(2*n) coincides with 3^(-1) (mod 2^(2*n)) given in A007583(n), n >= 1. - Wolfdieter Lang, Mar 12 2012
If an AVL tree has a leaf at depth n, then the tree can contain no more than a(n+1) nodes total. - Mike Rosulek, Nov 20 2012
Also, this is the Lucas sequence V(5, 4). - Bruno Berselli, Jan 10 2013
Also, for n > 0, a(n) is an odd number whose Collatz trajectory contains no odd number other than n and 1. - Jayanta Basu, Mar 24 2013
Sum_{n >= 1} 1/a(n) converges to (3*(log(4/3) - QPolyGamma[0, 1, 1/4]))/log(4) = 1.263293058100271... = A321873. - K. G. Stier, Jun 23 2014
Consider n spheres in R^n: the i-th one (i=1, ..., n) has radius r(i) = 2^(1-i) and the coordinates of its center are (0, 0, ..., 0, r(i), 0, ..., 0) where r(i) is in position i. The coordinates of the intersection point in the positive orthant of these spheres are (2/a(n), 4/a(n), 8/a(n), 16/a(n), ...). For example in R^2, circles centered at (1, 0) and (0, 1/2), and with radii 1 and 1/2, meet at (2/5, 4/5). - Jean M. Morales, May 19 2015
2*a(n) = A020988(n) gives the values of m such that binomial(4*m + 2, m) is odd.
4*a(n) = A080674(n) gives the values of m such that binomial(4*m + 4, m) is odd. (End)
Collatz Conjecture Corollary: Except for powers of 2, the Collatz iteration of any positive integer must eventually reach a(n) and hence terminate at 1. - Gregory L. Simay, May 09 2016
Number of active (ON, black) cells at stage 2^n - 1 of the two-dimensional cellular automaton defined by "Rule 598", based on the 5-celled von Neumann neighborhood. - Robert Price, May 16 2016
a(n) is also the number of coprime pairs of polynomials (f, g) over GF(2) where both f and g have degree n + 1 and nonzero constant term.
a(n) is also the number of pairs of one-dimensional binary cellular automata with linear and bipermutive local rule of neighborhood size n+1 giving rise to orthogonal Latin squares of order 2^m, where m is a multiple of n. (End)
Except for 0, 1 and 5, all terms are Brazilian repunits numbers in base 4, and so belong to A125134. For n >= 3, all these terms are composite because a(n) = {(2^n-1) * (2^n + 1)}/3 and either (2^n - 1) or (2^n + 1) is a multiple of 3. - Bernard Schott, Apr 29 2017
Given the 3 X 3 matrix A = [2, 1, 1; 1, 2, 1; 1, 1, 2] and the 3 X 3 unit matrix I_3, A^n = a(n)(A - I_3) + I_3. - Nicolas Patrois, Jul 05 2017
The binary expansion of a(n) (n >= 1) consists of n 1's alternating with n - 1 0's. Example: a(4) = 85 = 1010101_2. - Emeric Deutsch, Aug 30 2017
a(n) (n >= 1) is the viabin number of the integer partition [n, n - 1, n - 2, ..., 2, 1] (for the definition of viabin number see comment in A290253). Example: a(4) = 85 = 1010101_2; consequently, the southeast border of the Ferrers board of the corresponding integer partition is ENENENEN, where E = (1, 0), N = (0, 1); this leads to the integer partition [4, 3, 2, 1]. - Emeric Deutsch, Aug 30 2017
Numbers whose binary and Gray-code representations are both palindromes (i.e., intersection of A006995 and A281379). - Amiram Eldar, May 17 2021
Starting with n = 1 the sequence satisfies {a(n) mod 6} = repeat{1, 5, 3}. - Wolfdieter Lang, Jan 14 2022
Terms >= 5 are those q for which the multiplicative order of 2 mod q is floor(log_2(q)) + 2 (and which is 1 more than the smallest possible order for any q). - Tim Seuré, Mar 09 2024
The order of 2 modulo a(n) is 2*n for n >= 2. - Joerg Arndt, Mar 09 2024
|
|
|
REFERENCES
|
A. Fletcher, J. C. P. Miller, L. Rosenhead and L. J. Comrie, An Index of Mathematical Tables. Vols. 1 and 2, 2nd ed., Blackwell, Oxford and Addison-Wesley, Reading, MA, 1962, Vol. 1, p. 112.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 217.
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
|
|
|
|
FORMULA
|
a(n+1) = Sum_{m = 0..n} A060921(n, m).
G.f.: x/((1-x)*(1-4*x)). (End)
E.g.f.: (exp(4*x) - exp(x))/3. - Paul Barry, Mar 28 2003
a(n) = Sum_{i = 0..n-1} C(2*n - 1 - i, i)*2^i. - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004
a(n+1) = Sum_{k = 0..n} binomial(n+1, k+1)*3^k. - Paul Barry, Aug 20 2004
a(n) = center term in M^n * [1 0 0], where M is the 3 X 3 matrix [1 1 1 / 1 3 1 / 1 1 1]. M^n * [1 0 0] = [A007583(n-1) a(n) A007583(n-1)]. E.g., a(4) = 85 since M^4 * [1 0 0] = [43 85 43] = [A007583(3) a(4) A007583(3)]. - Gary W. Adamson, Dec 18 2004
a(n) = Sum_{k = 0..n, j = 0..n} C(n, j)*C(j, k)*A001045(j - k). - Paul Barry, Feb 15 2005
If we define f(m, j, x) = Sum_{k = j..m} binomial(m, k)*stirling2(k, j)*x^(m - k) then a(n-1) = f(2*n, 4, -2), n >= 2. - Milan Janjic, Apr 26 2009
a(n) = 4*a(n-1) + a(n-2) - 4*a(n-3) = 5*a(n-1) - 4*a(n-2), a(0) = 0, a(1) = 1, a(2) = 5. - Wolfdieter Lang, Oct 18 2010
a(n) = Sum_{k = 1..floor((n+2)/3)} C(2*n + 1, n + 2 - 3*k). - Mircea Merca, Jun 25 2011
Dirichlet g.f.: (PolyLog(s, 4) - zeta(s))/3. - Ilya Gutkovskiy, Jun 26 2016
a(m) divides a(m*n), in particular: a(2*n) == 0 (mod 5), a(3*n) == 0 (mod 3*7), a(5*n) == 0 (mod 11*31), etc. - M. F. Hasler, Oct 19 2018
a(n) = 4^(n-1) + a(n-1). - Bob Selcoe, Jan 01 2020
|
|
|
EXAMPLE
|
Apply Collatz iteration to 9: 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5 and hence 16, 8, 4, 2, 1.
Apply Collatz iteration to 27: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5 and hence 16, 8, 4, 2, 1. [Corrected by Sean A. Irvine at the suggestion of Stephen Cornelius, Mar 04 2024]
a(5) = (4^5 - 1)/3 = 341 = 11111_4 = {(2^5 - 1) * (2^5 + 1)}/3 = 31 * 33/3 = 31 * 11. - Bernard Schott, Apr 29 2017
|
|
|
MAPLE
|
[seq((4^n-1)/3, n=0..40)];
|
|
|
MATHEMATICA
|
LinearRecurrence[{5, -4}, {0, 1}, 30] (* Harvey P. Dale, Jun 23 2013 *)
|
|
|
PROG
|
(Magma) [n le 2 select n-1 else 5*Self(n-1)-4*Self(n-2): n in [1..70]]; // Vincenzo Librandi, Jun 13 2015
(PARI) a(n) = (4^n-1)/3;
(PARI) my(z='z+O('z^40)); Vec(z/((1-z)*(1-4*z))) \\ Altug Alkan, Oct 11 2015
(Haskell)
a002450 = (`div` 3) . a024036
a002450_list = iterate ((+ 1) . (* 4)) 0
(Maxima) makelist((4^n-1)/3, n, 0, 30); /* Martin Ettl, Nov 05 2012 */
(Scala) ((List.fill(20)(4: BigInt)).scanLeft(1: BigInt)(_ * _)).scanLeft(0: BigInt)(_ + _) // Alonso del Arte, Sep 17 2019
(Python)
|
|
|
CROSSREFS
|
Partial sums of powers of 4, A000302.
When converted to binary, this gives A094028.
Cf. A000225, A002446, A006995, A007583, A018215, A020988, A024036, A047849, A048716, A080355, A080674, A112627, A113860, A139391, A155701, A156605, A160967, A163834, A163868, A178415, A263132, A281379, A347834.
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A038548
|
|
Number of divisors of n that are at most sqrt(n).
|
|
+10
212
|
|
|
|
1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 3, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2, 2, 3, 1, 4, 1, 3, 2, 2, 2, 5, 1, 2, 2, 4, 1, 4, 1, 3, 3, 2, 1, 5, 2, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 6, 1, 2, 3, 4, 2, 4, 1, 3, 2, 4, 1, 6, 1, 2, 3, 3, 2, 4, 1, 5, 3, 2, 1, 6, 2, 2, 2, 4, 1, 6, 2, 3, 2, 2, 2, 6, 1, 3, 3, 5, 1, 4, 1, 4, 4
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
Number of ways to arrange n identical objects in a rectangle, modulo rotation.
Number of unordered solutions of x*y = n. - Colin Mallows, Jan 26 2002
Number of ways to write n-1 as n-1 = x*y + x + y, 0 <= x <= y <= n. - Benoit Cloitre, Jun 23 2002
Also number of values for x where x+2n and x-2n are both squares (e.g., if n=9, then 18+18 and 18-18 are both squares, as are 82+18 and 82-18 so a(9)=2); this is because a(n) is the number of solutions to n=k(k+r) in which case if x=r^2+2n then x+2n=(r+2k)^2 and x-2n=r^2 (cf. A061408). - Henry Bottomley, May 03 2001
Also number of sums of sequences of consecutive odd numbers or consecutive even numbers including sequences of length 1 (e.g., 12 = 5+7 or 2+4+6 or 12 so a(12)=3). - Naohiro Nomoto, Feb 26 2002
Number of partitions whose consecutive parts differ by exactly two.
a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24=2^3*3 and 375=3*5^3 both have prime signature (3,1). - Christian G. Bower, Jun 06 2005
Also number of partitions of n such that if k is the largest part, then each of the parts 1,2,...,k-1 occurs exactly twice. Example: a(12)=3 because we have [3,3,2,2,1,1],[2,2,2,2,2,1,1] and [1,1,1,1,1,1,1,1,1,1,1,1]. - Emeric Deutsch, Mar 07 2006
a(n) is also the number of nonnegative integer solutions of the Diophantine equation 4*x^2 - y^2 = 16*n. For example, a(24)=4 because there are 4 solutions: (x,y) = (10,4), (11,10), (14,20), (25,46). - N-E. Fahssi, Feb 27 2008
a(n) is the number of even divisors of 2*n that are <= sqrt(2*n). - Joerg Arndt, Mar 04 2010
Number of positive integers in the sequence defined by x_0 = n, x_(k+1) = (k+1)*(x_k-2)/(k+2) or equivalently by x_k = n/(k+1) - k. - Luc Rousseau, Mar 03 2018
Expanding the first comment: Number of rectangles with area n and integer side lengths, modulo rotation. Also number of 2D grids of n congruent squares, in a rectangle, modulo rotation (cf. A000005 for rectangles instead of squares; cf. A034836 for the 3D case). - Manfred Boergens, Jun 08 2021
Number of divisors of n that have an even number of prime divisors (counted with multiplicity), or in other words, number of terms of A028260 that divide n. - Antti Karttunen, Apr 17 2022
|
|
|
REFERENCES
|
George E. Andrews and Kimmo Eriksson, Integer Partitions, Cambridge Univ. Press, 2004, page 18, exer. 21, 22.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = ceiling(d(n)/2), where d(n) = number of divisors of n (A000005).
G.f.: Sum_{k>=1} x^(k^2)/(1-x^k). - Jon Perry, Sep 10 2004
Sum_{k=1..n} a(k) ~ n*log(n)/2 + (gamma - 1/2)*n, where gamma is Euler's constant (A001620). - Amiram Eldar, Nov 27 2022
|
|
|
EXAMPLE
|
a(4) = 2 since 4 = 2 * 2 = 4 * 1. Also A034178(4*4) = 2 since 16 = 4^2 - 0^2 = 5^2 - 3^2. - Michael Somos, May 11 2011
x + x^2 + x^3 + 2*x^4 + x^5 + 2*x^6 + x^7 + 2*x^8 + 2*x^9 + 2*x^10 + x^11 + ...
|
|
|
MAPLE
|
with(numtheory): A038548 := n->ceil(sigma[0](n)/2);
|
|
|
MATHEMATICA
|
Table[ Floor[ (DivisorSigma[0, n] + 1)/2], {n, 105}] (* Robert G. Wilson v, Mar 02 2009 *)
Table[Count[Divisors[n], _?(#<=Sqrt[n]&)], {n, 110}] (* Harvey P. Dale, Jul 10 2021 *)
|
|
|
PROG
|
(PARI) {a(n) = if( n<1, 0, sumdiv(n, d, d*d <= n))} /* Michael Somos, Jan 25 2005 */
(Haskell)
a038548 n = length $ takeWhile (<= a000196 n) $ a027750_row n
(C#)
System.Numerics.BigInteger erg = 0, i;
for (i = 1; i * i <= n; i++)
if (n % i == 0) erg++;
return (int)erg;
(Python)
from sympy import divisor_count
|
|
|
CROSSREFS
|
Inverse Möbius transform of A065043.
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A001349
|
|
Number of connected graphs with n nodes.
(Formerly M1657 N0649)
|
|
+10
166
|
|
|
|
1, 1, 1, 2, 6, 21, 112, 853, 11117, 261080, 11716571, 1006700565, 164059830476, 50335907869219, 29003487462848061, 31397381142761241960, 63969560113225176176277, 245871831682084026519528568, 1787331725248899088890200576580, 24636021429399867655322650759681644
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
The singleton graph K_1 is considered connected even though it is conventionally taken to have vertex connectivity 0. - Eric W. Weisstein, Jul 21 2020
Inverse Euler transform of A000088 but with a(0) omitted so that Sum_{k>=0} A000088(n) * x^n = Product_{k>0} (1 - x^k)^-a(k). It is debatable if there is a connected graph with 0 nodes and so a(0)=0 or better start from a(1)=1. - Michael Somos, Jun 01 2013. [As Harary once remarked in a famous paper ("Is the null-graph a pointless concept?"), the empty graph has every property, which is why a(0)=1. - N. J. A. Sloane, Apr 08 2014]
|
|
|
REFERENCES
|
P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp.
F. Harary and R. C. Read, Is the null-graph a pointless concept?, pp. 37-44 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, page 48, c(x). Also page 242.
Lupanov, O. B. Asymptotic estimates of the number of graphs with n edges. (Russian) Dokl. Akad. Nauk SSSR 126 1959 498--500. MR0109796 (22 #681).
Lupanov, O. B. "On asymptotic estimates of the number of graphs and networks with n edges." Problems of Cybernetics [in Russian], Moscow 4 (1960): 5-21.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1978.
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).
Robin J. Wilson, Introduction to Graph Theory, Academic Press, 1972. (But see A126060!)
|
|
|
LINKS
|
P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp. [Annotated scanned copy]
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Rodrigo Stange Tessinari, Marcia Helena Moreira Paiva, Maxwell E. Monteiro, Marcelo E. V. Segatto, Anilton Garcia, George T. Kanellos, Reza Nejabati, and Dimitra Simeonidou, On the Impact of the Physical Topology on the Optical Network Performance, IEEE British and Irish Conference on Optics and Photonics (BICOP 2018), London.
|
|
|
FORMULA
|
For asymptotics see Lupanov 1959, 1960, also Turner and Kautz, p. 18. - N. J. A. Sloane, Apr 08 2014
|
|
|
EXAMPLE
|
G.f. = 1 + x + x^2 + 2*x^3 + 6*x^4 + 21*x^5 + 112*x^6 + 853*x^7 + ....
|
|
|
MAPLE
|
# To produce all connected graphs on 4 nodes, for example (from N. J. A. Sloane, Oct 07 2013):
with(GraphTheory):
L:=[NonIsomorphicGraphs](4, output=graphs, outputform=adjacency, restrictto=connected):
|
|
|
MATHEMATICA
|
<<"Combinatorica`"; max = 19; A000088 = Table[ NumberOfGraphs[n], {n, 0, max}]; f[x_] = 1 - Product[ 1/(1 - x^k)^a[k], {k, 1, max}]; a[0] = a[1] = a[2] = 1; coes = CoefficientList[ Series[ f[x], {x, 0, max}], x]; sol = First[ Solve[ Thread[ Rest[ coes + A000088 ] == 0]]]; Table[ a[n], {n, 0, max}] /. sol (* Jean-François Alcover, Nov 24 2011 *)
terms = 20;
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a88[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
|
|
|
PROG
|
(Sage)
property=lambda G: G.is_connected()
def a(n):
return len([1 for G in graphs(n) if property(G)])
(Python)
from sympy import mobius, divisors
if n == 0: return 1
def c(n): return n*A000088(n)-sum(c(k)*A000088(n-k) for k in range(1, n))
return sum(mobius(n//d)*c(d) for d in divisors(n, generator=True))//n # Chai Wah Wu, Jul 02 2024
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,core,nice,changed
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
More terms from Ronald C. Read
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A061775
|
|
Number of nodes in rooted tree with Matula-Goebel number n.
|
|
+10
143
|
|
|
|
1, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 5, 5, 6, 5, 6, 6, 6, 6, 6, 7, 6, 7, 6, 6, 7, 6, 6, 7, 6, 7, 7, 6, 6, 7, 7, 6, 7, 6, 7, 8, 7, 7, 7, 7, 8, 7, 7, 6, 8, 8, 7, 7, 7, 6, 8, 7, 7, 8, 7, 8, 8, 6, 7, 8, 8, 7, 8, 7, 7, 9, 7, 8, 8, 7, 8, 9, 7, 7, 8, 8, 7, 8, 8, 7, 9, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 7, 8, 8, 8, 9, 7, 7, 9
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Let p(1)=2, ... denote the primes. The label f(T) for a rooted tree T is 1 if T has 1 node, otherwise f(T) = Product p(f(T_i)) where the T_i are the subtrees obtained by deleting the root and the edges adjacent to it. (Cf. A061773 for illustration).
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(1) = 1; if n = p_t (= the t-th prime), then a(n) = 1+a(t); if n = uv (u,v>=2), then a(n) = a(u)+a(v)-1.
|
|
|
EXAMPLE
|
a(4) = 3 because the rooted tree corresponding to the Matula-Goebel number 4 is "V", which has one root-node and two leaf-nodes, three in total.
See also the illustrations in A061773.
|
|
|
MAPLE
|
with(numtheory): a := proc (n) local u, v: u := n-> op(1, factorset(n)): v := n-> n/u(n): if n = 1 then 1 elif isprime(n) then 1+a(pi(n)) else a(u(n))+a(v(n))-1 end if end proc: seq(a(n), n = 1..108); # Emeric Deutsch, Sep 19 2011
|
|
|
MATHEMATICA
|
a[n_] := Module[{u, v}, u = FactorInteger[#][[1, 1]]&; v = #/u[#]&; If[n == 1, 1, If[PrimeQ[n], 1+a[PrimePi[n]], a[u[n]]+a[v[n]]-1]]]; Table[a[n], {n, 108}] (* Jean-François Alcover, Jan 16 2014, after Emeric Deutsch *)
|
|
|
PROG
|
(Haskell)
import Data.List (genericIndex)
a061775 n = genericIndex a061775_list (n - 1)
a061775_list = 1 : g 2 where
g x = y : g (x + 1) where
y = if t > 0 then a061775 t + 1 else a061775 u + a061775 v - 1
where t = a049084 x; u = a020639 x; v = x `div` u
(PARI)
A061775(n) = if(1==n, 1, if(isprime(n), 1+A061775(primepi(n)), {my(pfs, t, i); pfs=factor(n); pfs[, 1]=apply(t->A061775(t), pfs[, 1]); (1-bigomega(n)) + sum(i=1, omega(n), pfs[i, 1]*pfs[i, 2])}));
for(n=1, 10000, write("b061775.txt", n, " ", A061775(n)));
(Python)
from functools import lru_cache
from sympy import isprime, factorint, primepi
@lru_cache(maxsize=None)
if n == 1: return 1
if isprime(n): return 1+A061775(primepi(n))
return 1+sum(e*(A061775(p)-1) for p, e in factorint(n).items()) # Chai Wah Wu, Mar 19 2022
|
|
|
CROSSREFS
|
Sum of entries in row n of irregular table A214573.
Cf. A005517 (the position of the first occurrence of n).
Cf. A005518 (the position of the last occurrence of n).
Cf. A091233 (their difference plus one).
Cf. A214572 (Numbers k such that a(k) = 8).
Cf. also A000081, A061773, A049084, A020639, A049076, A078442, A091238, A091204, A091205, A109082, A127301, A109129, A193402, A193405, A193406, A196047, A196068, A198333, A206487, A206494, A206496, A214569, A214571, A213670, A214568, A228599, A245817, A245818.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A004394
|
|
Superabundant [or super-abundant] numbers: n such that sigma(n)/n > sigma(m)/m for all m < n, sigma(n) being A000203(n), the sum of the divisors of n.
|
|
+10
93
|
|
|
|
1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 10080, 15120, 25200, 27720, 55440, 110880, 166320, 277200, 332640, 554400, 665280, 720720, 1441440, 2162160, 3603600, 4324320, 7207200, 8648640, 10810800, 21621600
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Matthew Conroy points out that these are different from the highly composite numbers - see A002182. Jul 10 1996
With respect to the comment above, neither sequence is subsequence of the other. - Ivan N. Ianakiev, Feb 11 2020
Also n such that sigma_{-1}(n) > sigma_{-1}(m) for all m < n, where sigma_{-1}(n) is the sum of the reciprocals of the divisors of n. - Matthew Vandermast, Jun 09 2004
Ramanujan (1997, Section 59; written in 1915) called these numbers "generalized highly composite." Alaoglu and Erdős (1944) changed the terminology to "superabundant." - Jonathan Sondow, Jul 11 2011
Alaoglu and Erdős show that: (1) n is superabundant => n=2^{e_2} * 3^{e_3} * ...* p^{e_p}, with e_2 >= e_3 >= ... >= e_p (and e_p is 1 unless n=4 or n=36); (2) if q < r are primes, then | e_r - floor(e_q*log(q)/log(r)) | <= 1; (3) q^{e_q} < 2^{e_2+2} for primes q, 2 < q <= p. - _Keith Briggs_, Apr 26 2005
It follows from Alaoglu and Erdős finding 1 (above) that, for n > 7, a(n) is a Zumkeller Number (A083207); for details, see Proposition 9 and Corollary 5 at Rao/Peng link (below). - Ivan N. Ianakiev, Feb 11 2020
See A166735 for superabundant numbers that are not highly composite, and A189228 for superabundant numbers that are not colossally abundant.
Pillai called these numbers "highly abundant numbers of the 1st order". - Amiram Eldar, Jun 30 2019
|
|
|
REFERENCES
|
R. Honsberger, Mathematical Gems, M.A.A., 1973, p. 112.
J. Sandor, "Abundant numbers", In: M. Hazewinkel, Encyclopedia of Mathematics, Supplement III, Kluwer Acad. Publ., 2002 (see pp. 19-21).
D. Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, 128.
|
|
|
LINKS
|
S. Sivasankaranarayana Pillai, Highly abundant numbers, Bulletin of the Calcutta Mathematical Society, Vol. 35, No. 1 (1943), pp. 141-156.
S. Ramanujan, Highly composite numbers, Annotated and with a foreword by J.-L. Nicolas and G. Robin, Ramanujan J., 1 (1997), 119-153.
K. P. S. Bhaskara Rao and Yuejian Peng, On Zumkeller Numbers, Journal of Number Theory, Volume 133, Issue 4, April 2013, pp. 1135-1155.
|
|
|
FORMULA
|
|
|
|
MATHEMATICA
|
a=0; Do[b=DivisorSigma[1, n]/n; If[b>a, a=b; Print[n]], {n, 1, 10^7}]
(* Second program: convert all 8436 terms in b-file into a list of terms: *)
f[w_] := Times @@ Flatten@ {Complement[#1, Union[#2, #3]], Product[Prime@ i, {i, PrimePi@ #}] & /@ #2, Factorial /@ #3} & @@ ToExpression@ {StringSplit[w, _?(! DigitQ@ # &)], StringCases[w, (x : DigitCharacter ..) ~~ "#" :> x], StringCases[w, (x : DigitCharacter ..) ~~ "!" :> x]}; Map[Which[StringTake[#, 1] == {"#"}, f@ Last@ StringSplit@ Last@ #, StringTake[#, 1] == {}, Nothing, True, ToExpression@ StringSplit[#][[1, -1]]] &, Drop[Import["b004394.txt", "Data"], 3] ] (* Michael De Vlieger, May 08 2018 *)
|
|
|
PROG
|
(PARI) print1(r=1); forstep(n=2, 1e6, 2, t=sigma(n, -1); if(t>r, r=t; print1(", "n))) \\ Charles R Greathouse IV, Jul 19 2011
|
|
|
CROSSREFS
|
The colossally abundant numbers A004490 are a subsequence, as are A023199.
Subsequence of A025487; apart from a(3) = 4 and a(7) = 36, a subsequence of A102750.
Cf. A112974 (number of superabundant numbers between colossally abundant numbers).
Cf. A091901 (Robin's inequality), A189686 (superabundant and the reverse of Robin's inequality), A192884 (non-superabundant and the reverse of Robin's inequality).
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A109129
|
|
Width (i.e., number of non-root vertices having degree 1) of the rooted tree with Matula-Goebel number n.
|
|
+10
75
|
|
|
|
0, 1, 1, 2, 1, 2, 2, 3, 2, 2, 1, 3, 2, 3, 2, 4, 2, 3, 3, 3, 3, 2, 2, 4, 2, 3, 3, 4, 2, 3, 1, 5, 2, 3, 3, 4, 3, 4, 3, 4, 2, 4, 3, 3, 3, 3, 2, 5, 4, 3, 3, 4, 4, 4, 2, 5, 4, 3, 2, 4, 3, 2, 4, 6, 3, 3, 3, 4, 3, 4, 3, 5, 3, 4, 3, 5, 3, 4, 2, 5, 4, 3, 2, 5, 3, 4, 3, 4, 4, 4, 4, 4, 2, 3, 4, 6, 2, 5, 3, 4
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
The Matula-Goebel number of a rooted tree is defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m >= 2 there corresponds the product of the Matula-Goebel numbers of the m branches of T.
A non-root vertex having degree 1 is called a leaf.
Every positive integer has a unique factorization (see A324924) into factors q(i) = prime(i)/i for i > 0. The number of ones in this factorization is a(n). For example, 30 = q(1)^3 q(2)^2 q(3), so a(30) = 3. - Gus Wiseman, Mar 23 2019
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(1)=0; a(2)=1; if n = p(t) (= the t-th prime) and t >= 2, then a(n) = a(t); if n = rs (r, s >= 2), then a(n) = a(r) + a(s). The Maple program is based on this recursive formula.
The Gutman et al. references contain a different recursive formula.
|
|
|
EXAMPLE
|
a(7)=2 because the rooted tree with Matula-Goebel number 7 is the rooted tree Y.
a(2^m) = m because the rooted tree with Matula-Goebel number 2^m is a star with m edges.
|
|
|
MAPLE
|
with(numtheory): a := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 0 elif n = 2 then 1 elif bigomega(n) = 1 then a(pi(n)) else a(r(n))+a(s(n)) end if end proc: seq(a(n), n = 1 .. 110);
|
|
|
MATHEMATICA
|
Nest[Function[{a, n}, Append[a, If[PrimeQ@ n, a[[PrimePi@ n]], Total@ Map[#2 a[[#1]] & @@ # &, FactorInteger[n]] ]]] @@ {#, Length@ # + 1} &, {0, 1}, 105] (* Michael De Vlieger, Mar 24 2019 *)
|
|
|
PROG
|
(Haskell)
import Data.List (genericIndex)
a109129 n = genericIndex a109129_list (n - 1)
a109129_list = 0 : 1 : g 3 where
g x = y : g (x + 1) where
y = if t > 0 then a109129 t else a109129 r + a109129 s
where t = a049084 x; r = a020639 x; s = x `div` r
(PARI) ML(n) = if( n==1, 1, my(f=factor(n)); sum(k=1, matsize(f)[1], ML(primepi(f[k, 1]))*f[k, 2])) ;
(Python)
from functools import lru_cache
from sympy import primepi, isprime, factorint
@lru_cache(maxsize=None)
if n <= 2: return n-1
if isprime(n): return A109129(primepi(n))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
_Keith Briggs_, Aug 17 2005
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.166 seconds
|
