|
%I #43 Jul 21 2023 04:29:26
%S 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,
%T 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,
%U 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
%N a(n) is the number of Jacobsthal numbers (A001045) needed to sum to n using the greedy algorithm.
%C Sum of digits in "Jacobsthal greedy base", A265747.
%C 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.
%C 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
%H Antti Karttunen, <a href="/A265745/b265745.txt">Table of n, a(n) for n = 0..10923</a>
%F a(0) = 0; for n >= 1, a(n) = 1 + a(n - A001045(A130249(n))). [This formula uses a simple greedy algorithm.]
%e a(0) = 0, because no numbers are needed to form an empty sum, which is zero.
%e For n=1 we need just A001045(2) = 1, thus a(1) = 1.
%e For n=2 we need A001045(2) + A001045(2) = 1 + 1, thus a(2) = 2.
%e For n=4 we need A001045(3) + A001045(2) = 3 + 1, thus a(4) = 2.
%e 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.
%e For n=7 we need A001045(4) + A001045(2) + A001045(2) = 5 + 1 + 1, thus a(7) = 3.
%e For n=8 we need A001045(4) + A001045(3) = 5 + 3, thus a(8) = 2.
%e For n=10 we need A001045(4) + A001045(4) = 5 + 5, thus a(10) = 2.
%t 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 *)
%o (Scheme, with memoization-macro definec)
%o (definec (A265745 n) (if (zero? n) n (+ 1 (A265745 (- n (A001045 (A130249 n)))))))
%o (Python)
%o def greedyJ(n): n1 = (3*n+1).bit_length() - 1; return (2**n1 - (-1)**n1)//3
%o def a(n): return 0 if n == 0 else 1 + a(n - greedyJ(n))
%o print([a(n) for n in range(107)]) # _Michael S. Branicky_, Jul 11 2021
%o (PARI)
%o A130249(n) = floor(log(3*n + 1)/log(2));
%o A001045(n) = (2^n - (-1)^n) / 3;
%o A265745(n) = {if(n == 0, 0, my(d = n - A001045(A130249(n))); if(d == 0, 1, 1 + A265745(d)));} \\ _Amiram Eldar_, Jul 21 2023
%Y Cf. A001045, A130249, A197911, A003158, A265746, A265747.
%Y Cf. also A007895, A014420, A053610, A265404, A265743, A265744.
%K nonn,base
%O 0,3
%A _Antti Karttunen_, Dec 17 2015
|
