A309978 -id:A309978 - cp's OEIS frontend

A328422 Number of paths from 2 to n via maps of the form x -> x + x^j, where j is a nonnegative integer.

1, 1, 2, 2, 4, 4, 6, 6, 9, 9, 14, 14, 18, 18, 24, 24, 31, 31, 42, 42, 51, 51, 65, 65, 79, 79, 97, 97, 118, 118, 142, 142, 167, 167, 198, 198, 229, 229, 271, 271, 317, 317, 368, 368, 419, 419, 484, 484, 549, 549, 628, 628, 707, 707, 808, 808, 905, 905, 1023

Offset: 2

Peter Kagey, Oct 15 2019

nonn

This sequence is essentially the same as the number of paths from 1 to n. However, starting from 2 removes the ambiguity of how many maps there are from 1 to 2.

a(2n+1) = a(2n) for all n because x + x^j is odd if and only if x is even and j = 0.

			For n = 8 the a(8) = 6 paths are:
2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 with j = [0,0,0,0,0,0]
2 -> 3 -> 4 -> 8                with j = [0,0,1]
2 -> 3 -> 6 -> 7 -> 8           with j = [0,1,0,0]
2 -> 4 -> 5 -> 6 -> 7 -> 8      with j = [1,0,0,0,0]
2 -> 4 -> 8                     with j = [1,1]
2 -> 6 -> 7 -> 8                with j = [2,0,0]

Peter Kagey, Table of n, a(n) for n = 2..10000

Cf. A307074, A307092, A309997, A309978.

a(2) = 1, a(n) = Sum_{k=1..A309978(n)} a(A328446(n,k)) for n > 2.

A328446 Table read by rows: the n-th row gives the nonnegative integers k such that n - k is a power of k.

Original entry on oeis.org

0, 1, 2, 2, 3, 4, 2, 3, 5, 6, 4, 7, 8, 2, 5, 9, 10, 3, 6, 11, 12, 7, 13, 14, 8, 15, 16, 2, 9, 17, 18, 4, 10, 19, 20, 11, 21, 22, 12, 23, 24, 13, 25, 26, 14, 27, 28, 3, 5, 15, 29, 30, 16, 31, 32, 2, 17, 33, 34, 18, 35, 36, 19, 37, 38, 20, 39, 40, 6, 21, 41, 42, 22

Offset: 1

Peter Kagey, Oct 15 2019

The n-th row has length A309978(n) for n > 1.

			Table begins
   n | n-th row
  ---+----------
   1 | 0
   2 | 1
   3 | 2
   4 | 2, 3
   5 | 4
   6 | 2, 3, 5
   7 | 6
   8 | 4, 7
   9 | 8
  10 | 2, 5, 9
  11 | 10
  12 | 3, 6, 11
  13 | 12
  14 | 7, 13
  15 | 14
  16 | 8, 15
  17 | 16
  18 | 2, 9, 17
For n = 10 the 10th row is 2, 5, 9 because
10 - 2 = 2^3,
10 - 5 = 5^1, and
10 - 9 = 9^0.

Peter Kagey, Table of n, a(n) for n = 1..10000

Cf. A307092, A309978.

row(n) = {if (n==1, return ([0])); my(row = vector(0)); fordiv(n, d, if ((d>1) && (dMichel Marcus, Oct 16 2019

cp's OEIS Frontend

A328422 Number of paths from 2 to n via maps of the form x -> x + x^j, where j is a nonnegative integer.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula