A328480 -id:A328480 - cp's OEIS frontend

A328481 Number of terms required when n is expressed as a greedy sum of terms of A129912 (digital sum of n when written in greedy A129912-base).

0, 1, 1, 2, 2, 3, 1, 2, 2, 3, 3, 4, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, 2, 3, 3, 4, 4, 5, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, 2, 3, 3, 4, 4, 5, 3, 4, 4, 5, 5, 6, 3, 4, 4, 5, 5, 6, 1, 2, 2, 3, 3, 4, 2, 3, 3, 4, 4, 5, 2, 3, 3, 4, 4, 5, 3, 4, 4, 5, 5, 6, 3, 4, 4, 5, 5, 6, 2, 3, 3, 4, 4, 5, 3, 4, 4, 5, 5, 6, 3, 4, 4, 5

Offset: 0

Antti Karttunen, Oct 19 2019

nonn

			Terms of A129912 (numbers that are products of distinct primorial numbers) begin as: 1, 2, 6, 12, 30, 60, 180, 210, 360, 420, 1260, ...
Number 5 is expressed as 5 = 2 + 2 + 1 when always choosing the largest term which is <= {what is remaining of the original number}. Thus a(5) = 3.
Number 21 is expressed as 21 = 12 + 6 + 2 + 1, thus a(21) = 4.
Number 720 is expressed as 720 = 420 + 210 + 60 + 30, thus a(720) = 4. Note that 720 = 2*360, so in this case the greedy algorithm does not produce an optimal result.

Antti Karttunen, Table of n, a(n) for n = 0..30030
Index entries for sequences related to primorial numbers

Cf. A002110, A129912, A328480, A328482, A328483.

Cf. also A276150.

isA129912(n) = { my(o=valuation(n, 2), t); if(o<1||n<2, return(n==1)); n>>=o; forprime(p=3, , t=valuation(n, p); n/=p^t; if(t>o || tA129912
prepare_A129912_upto(n) = { my(xs=List([]), k=0); while(kA129912(k), listput(xs,k))); List(Vecrev(xs)); };
number_of_terms_in_greedy_sum(n,terms) = { my(c=0); while(n,if(terms[1] > n, listpop(terms,1), c += (n\terms[1]); n %= terms[1])); (c); };
number_of_terms_in_greedy_sum_v1(n,terms) = { my(c=0); while(n,if(terms[1] > n, listpop(terms,1), n -= terms[1]; c++)); (c); }; \\ (Simpler variant)
A328481(n) = number_of_terms_in_greedy_sum(n,prepare_A129912_upto(n));

a(0) = 0; and for n > 0, a(n) = 1 + a(A328480(n)).
a(A129912(n)) = a(A002110(n)) = 1.
For all n, a(n) >= A328482(n).

cp's OEIS Frontend

A328481 Number of terms required when n is expressed as a greedy sum of terms of A129912 (digital sum of n when written in greedy A129912-base).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula