cp's OEIS Frontend

A372555 Least number of Jacobsthal numbers that add up to n.

%I A372555 #16 May 10 2024 11:00:07
%S A372555 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 A372555 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,3,2,3,4,3,
%U A372555 4,3,4,5,4,5,4,3,4,5,4,5,4,5,6,5,4,1,2,3,2,3,2,3,4,3,4,3,2,3,4,3,4,3,4,5,4,5,2
%N A372555 Least number of Jacobsthal numbers that add up to n.
%C A372555 Differs from A265745 for the first time at n=63, where a(63) = 3, while A265745(63) = 5. The next differences occur at n=84, 148, 169, 191, 212, 234, 255, etc. See A372557.
%C A372555 See conjecture in A372556, and also in A372561.
%H A372555 Antti Karttunen, <a href="/A372555/b372555.txt">Table of n, a(n) for n = 0..87381</a>
%F A372555 a(0) = 0, a(1) = 1; for n > 1, a(n) = 1 + a(n-A001045(A372556(n))).
%e A372555 a(5) = 1, because 5 is itself in A001045.
%e A372555 a(7) = 3, because 7 can be expressed as a sum of three Jacobsthal numbers, either as 5+1+1 or 3+3+1, but not as a sum of two Jacobsthal numbers, and neither 7 is itself in A001045.
%e A372555 a(63) = 3, because the least number of Jacobsthal numbers that add up to 63 is obtained when we use A001045(6) = 21 three times, as 21+21+21 = 63. This is the first time this sequence differs from A265745.
%o A372555 (PARI)
%o A372555 up_to = 87381; \\ = A001045(18).
%o A372555 A001045(n) = (2^n - (-1)^n) / 3;
%o A372555 A130249(n) = (#binary(3*n+1)-1);
%o A372555 A372555_or_556list(up_to_n,return_556_instead) = { my(v372555 = vector(up_to_n), v372556 = vector(up_to_n)); v372555[1] = 1; v372556[1] = 2; for(n=2,#v372556, my(m=-1,mk=-1,s=A130249(n)); if(A001045(s)==n, v372555[n] = 1; v372556[n] = s, forstep(k=s, 1, -1, my(c=v372555[n-A001045(k)]); if(m<0 || c<m, m=c; mk=k)); v372556[n] = mk; v372555[n] = 1+v372555[n-A001045(mk)])); if(return_556_instead,v372556,v372555); };
%o A372555 v372555 = A372555_or_556list(up_to,0);
%o A372555 A372555(n) = if(!n,n,v372555[n]);
%o A372555 (Scheme)
%o A372555 ;; An implementation of memoization-macro definec can be found for example in: http://oeis.org/wiki/Memoization
%o A372555 (definec (A001045 n) (if (<= n 1) n (+ (A001045 (- n 1)) (* 2 (A001045 (- n 2))))))
%o A372555 (define (A130249 n) (floor->exact (/ (log (+ 1 (* 3 n))) (log 2))))
%o A372555 (define (A147612 n) (if (<= n 1) 1 (if (= (A001045 (A130249 n)) n) 1 0)))
%o A372555 (definec (A372555 n) (if (<= n 1) n (+ 1 (A372555 (- n (A001045 (A372556 n)))))))
%o A372555 (definec (A372556 n) (let ((k (A130249 n))) (if (= 1 (A147612 n)) k (let loop ((k k) (m #f) (mk #f)) (cond ((zero? k) mk) (else (let* ((c (A372555 (- n (A001045 k))))) (if (or (not m) (< c m)) (loop (- k 1) c k) (loop (- k 1) m mk)))))))))
%Y A372555 Cf. A001045, A130249, A147612, A372556, A372557, A372561.
%Y A372555 Cf. also A265745.
%K A372555 nonn
%O A372555 0,3
%A A372555 _Antti Karttunen_, May 07 2024