A281145 Number of same-trees of weight n.

1, 2, 2, 6, 2, 14, 2, 54, 10, 38, 2, 494, 2, 134, 42, 4470, 2, 3422, 2, 10262, 138, 2054, 2, 490926, 34, 8198, 1514, 314294, 2, 628318, 2, 30229110, 2058, 131078, 162, 150147342, 2, 524294, 8202, 628073814, 2, 109952254, 2, 371210294, 207370, 8388614, 2

Offset

1,2

Comments

A same-tree is either: (case 1) a positive integer, or (case 2) a finite sequence of two or more same-trees all having the same weight, where the weight in case 2 is the sum of weights.

Links

G. C. Greubel, Table of n, a(n) for n = 1..4000

Formula

a(n) = 1 + Sum a(d)^(n/d) where the sum is over divisors less than n.

Example

The a(6)=14 same-trees are:
6,
(33),
(222),
(3(111)), ((111)3),
(22(11)), (2(11)2), ((11)22),
(2(11)(11)), ((11)2(11)), ((11)(11)2),
((111)(111)), ((11)(11)(11)), (111111).
The a(9)=10 same-trees are:
9,
(333),
(33(111)), (3(111)3), ((111)33),
(3(111)(111)), ((111)3(111)), ((111)(111)3),
((111)(111)(111)), (111111111).

Mathematica

a[n_]:=1+DivisorSum[n, b[#]^(n/#)&]-b[n]/.b->a;
Array[a, 47]

Prog

(PARI) seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + sumdiv(n, d, v[n/d]^d)); v} \\ Andrew Howroyd, Aug 20 2018

Crossrefs

Cf. A196545, A260685, A273873, A275870, A006241.

Sequence in context: A249631 A055934 A096217 * A098555 A057562 A102628

Adjacent sequences: A281142 A281143 A281144 * A281146 A281147 A281148

Keyword

nonn

Author

Gus Wiseman, Jan 15 2017

Status

approved