A265745 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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

Positions where a(n) is different from A372555(n) are n=63, 84, 148, 169, 191, 212, 234, 255, etc. See A372557. - Antti Karttunen, May 07 2024

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