A300647 Number of same-trees of weight n in which all outdegrees are odd.

1, 1, 2, 1, 2, 2, 2, 1, 10, 2, 2, 2, 2, 2, 42, 1, 2, 10, 2, 2, 138, 2, 2, 2, 34, 2, 1514, 2, 2, 42, 2, 1, 2058, 2, 162, 10, 2, 2, 8202, 2, 2, 138, 2, 2, 207370, 2, 2, 2, 130, 34, 131082, 2, 2, 1514, 2082, 2, 524298, 2, 2, 42, 2, 2, 14725738, 1, 8226, 2058, 2

Offset

1,3

Comments

A same-tree of weight n > 0 is either a single node of weight n, or a finite sequence of two or more same-trees whose weights are all equal and sum to n.

Links

Antti Karttunen, Table of n, a(n) for n = 1..8192

Formula

a(n) = 1 + Sum_d a(n/d)^d where the sum is over odd divisors of n greater than 1.

Example

The a(9) = 10 odd same-trees:
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+Sum[a[n/d]^d, {d, Select[Rest[Divisors[n]], OddQ]}];
Array[a, 80]

Prog

(PARI) a(n) = if (n==1, 1, 1+sumdiv(n, d, if ((d > 1) && (d % 2), a(n/d)^d))); \\ Michel Marcus, Mar 10 2018

Crossrefs

Cf. A003238, A006241, A063834, A069283, A273873, A281145, A289078, A289079, A289501, A298118, A300436, A300439, A300574, A300648, A300649, A300650.

Sequence in context: A300648 A318450 A120256 * A114811 A275675 A219025

Adjacent sequences: A300644 A300645 A300646 * A300648 A300649 A300650

Keyword

nonn

Author

Gus Wiseman, Mar 10 2018

Status

approved