login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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).
4
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,4
FORMULA
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).
EXAMPLE
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.
PROG
(PARI)
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 || t<o-1, return(0)); if(t==0, return(n==1)); o=t); }; \\ From A129912
prepare_A129912_upto(n) = { my(xs=List([]), k=0); while(k<n, k++; if(isA129912(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));
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen, Oct 19 2019
STATUS
approved