cp's OEIS Frontend

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

%I A265745 #55 May 07 2024 17:40:00
%S A265745 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 A265745 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 A265745 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 A265745 a(n) is the number of Jacobsthal numbers (A001045) needed to sum to n using the greedy algorithm.
%C A265745 Sum of digits in "Jacobsthal greedy base", A265747.
%C A265745 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 A265745 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
%C A265745 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
%H A265745 Antti Karttunen, <a href="/A265745/b265745.txt">Table of n, a(n) for n = 0..10923</a>
%F A265745 a(0) = 0; for n >= 1, a(n) = 1 + a(n - A001045(A130249(n))). [This formula uses a simple greedy algorithm.]
%e A265745 a(0) = 0, because no numbers are needed to form an empty sum, which is zero.
%e A265745 For n=1 we need just A001045(2) = 1, thus a(1) = 1.
%e A265745 For n=2 we need A001045(2) + A001045(2) = 1 + 1, thus a(2) = 2.
%e A265745 For n=4 we need A001045(3) + A001045(2) = 3 + 1, thus a(4) = 2.
%e A265745 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 A265745 For n=7 we need A001045(4) + A001045(2) + A001045(2) = 5 + 1 + 1, thus a(7) = 3.
%e A265745 For n=8 we need A001045(4) + A001045(3) = 5 + 3, thus a(8) = 2.
%e A265745 For n=10 we need A001045(4) + A001045(4) = 5 + 5, thus a(10) = 2.
%t A265745 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 A265745 (Scheme, with memoization-macro definec)
%o A265745 (definec (A265745 n) (if (zero? n) n (+ 1 (A265745 (- n (A001045 (A130249 n)))))))
%o A265745 (Python)
%o A265745 def greedyJ(n): n1 = (3*n+1).bit_length() - 1; return (2**n1 - (-1)**n1)//3
%o A265745 def a(n): return 0 if n == 0 else 1 + a(n - greedyJ(n))
%o A265745 print([a(n) for n in range(107)]) # _Michael S. Branicky_, Jul 11 2021
%o A265745 (PARI)
%o A265745 A130249(n) = floor(log(3*n + 1)/log(2));
%o A265745 A001045(n) = (2^n - (-1)^n) / 3;
%o A265745 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 A265745 Cf. A001045, A130249, A197911, A003158, A265746, A265747, A364377, A364379, A364380, A372288, A372555, A372557.
%Y A265745 Cf. A054111 (apparently the positions of the first occurrence of each n > 0).
%Y A265745 Cf. also A007895, A014420, A053610, A265404, A265743, A265744.
%K A265745 nonn,base
%O A265745 0,3
%A A265745 _Antti Karttunen_, Dec 17 2015