A309616 a(n) is the number of ways to represent 2*n in the decibinary system.

1, 2, 4, 6, 10, 13, 18, 22, 30, 36, 45, 52, 64, 72, 84, 93, 110, 122, 140, 154, 177, 192, 214, 230, 258, 277, 304, 324, 356, 376, 405, 426, 464, 490, 528, 557, 604, 634, 678, 710, 765, 802, 854, 892, 952, 989, 1042, 1080, 1146, 1190, 1253, 1300, 1374, 1420, 1486, 1533, 1612, 1664

Offset

0,2

Comments

It appears that a(n) is the number of decibinary numbers that can be constructed to represent the decimal numbers 2n-2 and 2n-1. To make this more clear let's consider n = 5: a(5) = 10 means that there are 10 decibinary numbers that represent the decimal numbers 2*5 - 2 = 8 and 2*5 - 1 = 9.

Furthermore, a(n) is the number of k such that A028897(k)=2*n.

Links

Table of n, a(n) for n=0..57.

HackerRank, Decibinary Numbers.

Sela Fried, Proof of a recurrence for A309616, 2026.

Formula

a(1) = 1. a(n) = a(n-1) + a(ceiling(n/2)) if 1 < n <= 5.

Conjecture: a(n) = a(n-1) + a(ceiling(n/2)) - a(ceiling((n-5)/2)) if n > 5.

I think this sequence is closely related to the 10th binary partition function. The only difference is that every second number is omitted. At the moment, the 10th binary partition function is not in the OEIS. However, my experiments strongly suggest that the 10th binary partition function would indeed look like 1, 1, 2, 2, 4, 4, 6, 6, 10, 10, 13, 13, ...

The conjectured recurrence is true (see Fried link). - Sela Fried, Mar 21 2026

Example

a(1) = 1.
a(2) = a(2-1) + a(ceiling(2/2)) = a(1) + a(1) = 1 + 1 = 2.
a(3) = a(3-1) + a(ceiling(3/2)) = a(2) + a(2) = 2 + 2 = 4.
a(4) = a(4-1) + a(ceiling(4/2)) = a(3) + a(2) = 4 + 2 = 6.
a(5) = a(5-1) + a(ceiling(5/2)) = a(4) + a(3) = 6 + 4 = 10.
a(6) = a(6-1) + a(ceiling(6/2)) - a(ceiling((6-5)/2)) = a(5) + a(3) - a(1) = 10 + 4 - 1 = 13.
a(7) = a(7-1) + a(ceiling(7/2)) - a(ceiling((7-5)/2)) = a(6) + a(4) - a(1) = 13 + 6 - 1 = 18.
a(8) = a(8-1) + a(ceiling(8/2)) - a(ceiling((8-5)/2)) = a(7) + a(4) - a(2) = 18 + 6 - 2 = 22.
a(9) = a(9-1) + a(ceiling(9/2)) - a(ceiling((9-5)/2)) = a(8) + a(5) - a(2) = 22 + 10 - 2 = 30.
a(10) = a(10-1) + a(ceiling(10/2)) - a(ceiling((10-5)/2)) = a(9) + a(5) - a(3) = 30 + 10 - 4 = 36.

Mathematica

Nest[Append[#1, #1[[-1]] + #1[[Ceiling[#2/2] ]] - If[#2 > 5, #1[[Ceiling[(#2 - 5)/2] ]], 0 ]] & @@ {#, Length@ # + 1} &, {1}, 57] (* Michael De Vlieger, Sep 29 2019 *)

Prog

(C++) int a(int n) {
    std::vector<int> seq;
    int a = 1;
    seq.push_back(a);
    for (int i = 1; i < n; i++) {
        a += seq.at(i / 2);
        a -= (i >= 5) ? seq.at((i - 5) / 2) : 0;
        seq.push_back(a);
    }
    return seq.back();
}

Crossrefs

Cf. A007728: superseeker found that the deltas of the sequence a(n+1) - a(n) match transformations of the original query.

Cf. A028897.

Sequence in context: A275489 A153817 A354673 * A365321 A267452 A140652

Adjacent sequences: A309613 A309614 A309615 * A309617 A309618 A309619

Keyword

nonn,base

Author

Jonas Hollm, Aug 10 2019

Extensions

Name corrected by Rémy Sigrist, Oct 15 2019

Status

approved