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
Examples
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.
Links
- Antti Karttunen, Table of n, a(n) for n = 0..10923
Crossrefs
Programs
-
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 *)
-
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
-
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
Comments