A265745 a(n) is the number of Jacobsthal numbers (A001045) needed to sum to n using the greedy algorithm.

0, 1, 2, 1, 2, 1, 2, 3, 2, 3, 2, 1, 2, 3, 2, 3, 2, 3, 4, 3, 4, 1, 2, 3, 2, 3, 2, 3, 4, 3, 4, 3, 2, 3, 4, 3, 4, 3, 4, 5, 4, 5, 2, 1, 2, 3, 2, 3, 2, 3, 4, 3, 4, 3, 2, 3, 4, 3, 4, 3, 4, 5, 4, 5, 2, 3, 4, 3, 4, 3, 4, 5, 4, 5, 4, 3, 4, 5, 4, 5, 4, 5, 6, 5, 6, 1, 2, 3, 2, 3, 2, 3, 4, 3, 4, 3, 2, 3, 4, 3, 4, 3, 4, 5, 4, 5, 2

Offset

0,3

Comments

Sum of digits in "Jacobsthal greedy base", A265747.

It would be nice to know for sure whether this sequence gives also the least number of Jacobsthal numbers that add to n, i.e., that there cannot be even better nongreedy solutions.

The integer 63=21+21+21 has 3 for its 'non-greedy' solution, and a(63) = 5 for its greedy solution 63=43+11+5+3+1. - Yuriko Suwa, Jul 11 2021

Links

Antti Karttunen, Table of n, a(n) for n = 0..10923

Formula

a(0) = 0; for n >= 1, a(n) = 1 + a(n - A001045(A130249(n))). [This formula uses a simple greedy algorithm.]

Example

a(0) = 0, because no numbers are needed to form an empty sum, which is zero.
For n=1 we need just A001045(2) = 1, thus a(1) = 1.
For n=2 we need A001045(2) + A001045(2) = 1 + 1, thus a(2) = 2.
For n=4 we need A001045(3) + A001045(2) = 3 + 1, thus a(4) = 2.
For n=6 we form the greedy sum as A001045(4) + A001045(2) = 5 + 1, thus a(6) = 2. Alternatively, we could form the sum as A001045(3) + A001045(3) = 3 + 3, but the number of summands in that case is no less.
For n=7 we need A001045(4) + A001045(2) + A001045(2) = 5 + 1 + 1, thus a(7) = 3.
For n=8 we need A001045(4) + A001045(3) = 5 + 3, thus a(8) = 2.
For n=10 we need A001045(4) + A001045(4) = 5 + 5, thus a(10) = 2.

Mathematica

jacob[n_] := (2^n - (-1)^n)/3; maxInd[n_] := Floor[Log2[3*n + 1]]; A265745[n_] := A265745[n] = 1 + A265745[n - jacob[maxInd[n]]]; A265745[0] = 0; Array[A265745, 100, 0] (* Amiram Eldar, Jul 21 2023 *)

Prog

(Scheme, with memoization-macro definec)
(definec (A265745 n) (if (zero? n) n (+ 1 (A265745 (- n (A001045 (A130249 n)))))))
(Python)
def greedyJ(n): n1 = (3*n+1).bit_length() - 1; return (2**n1 - (-1)**n1)//3
def a(n): return 0 if n == 0 else 1 + a(n - greedyJ(n))
print([a(n) for n in range(107)]) # Michael S. Branicky, Jul 11 2021
(PARI)
A130249(n) = floor(log(3*n + 1)/log(2));
A001045(n) = (2^n - (-1)^n) / 3;
A265745(n) = {if(n == 0, 0, my(d = n - A001045(A130249(n))); if(d == 0, 1, 1 + A265745(d))); } \\ Amiram Eldar, Jul 21 2023

Crossrefs

Cf. A001045, A130249, A197911, A003158, A265746, A265747.

Cf. also A007895, A014420, A053610, A265404, A265743, A265744.

Sequence in context: A174713 A129985 A085243 * A092243 A257564 A194509

Adjacent sequences: A265742 A265743 A265744 * A265746 A265747 A265748

Keyword

nonn,base

Author

Antti Karttunen, Dec 17 2015

Status

approved