A276328 Digit sum when n is expressed in greedy A001563-base (A276326).

0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6, 4, 5, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6, 4, 5, 6, 7, 5, 6, 2, 3, 4, 5, 3, 4, 5, 6, 4, 5, 6, 7, 5, 6, 7, 8, 6, 7, 3, 4, 5, 6, 4, 5, 6, 7, 5, 6, 7, 8, 6, 7, 8, 9, 7, 8, 4, 5, 6, 7, 5, 6, 7, 8, 6, 7, 8, 9, 7, 8, 9, 10, 8, 9, 5, 6, 7, 8, 6, 7, 1

Offset

0,3

Comments

a(n) is the number of terms of A001563 needed to sum to n using the greedy algorithm.

This seems to give also the minimal number of terms of A001563 that sum to n (checked empirically up to n=3265920), but it would be nice to know for sure whether this holds for all n.

Links

Antti Karttunen, Table of n, a(n) for n = 0..4320

Formula

a(0) = 0; for n >= 1, a(n) = 1 + a(n-A258199(n)).

a(0) = 0; for n >= 1, a(n) = A276333(n) + a(A276335(n)).

Other identities and observations. For all n >= 0:

a(A276091(n)) = A000120(n).

a(n) >= A276337(n).

It also seems that a(n) <= A276332(n) for all n.

Example

For n=1, the largest term of A001563 <= 1 is A001563(1) = 1, thus a(1) = 1.
For n=2, the largest term of A001563 <= 2 is A001563(1) = 1, thus a(2) = 1 + a(2-1) = 2.
For n=18, the largest term of A001563 <= 18 is A001563(3) = 18, thus a(18) = 1.
For n=20, the largest term of A001563 <= 20 is A001563(3) = 18, thus a(20) = 1 + a(20-18) = 3.
For n=36, the largest term of A001563 <= 36 is A001563(3) = 18, thus a(36) = 1 + a(18) = 2.

Mathematica

f[n_] := Block[{a = {{0, n}}}, Do[AppendTo[a, {First@ #, Last@ #} &@ QuotientRemainder[a[[-1, -1]], (# #!) &[# - i]]], {i, 0, # - 1}] &@NestWhile[# + 1 &, 0, (# #!) &[# + 1] <= n &]; Rest[a][[All, 1]]]; {0}~Join~Table[Total@ f@ n, {n, 120}] (* Michael De Vlieger, Aug 31 2016 *)

Prog

(Scheme, with memoization-macro definec, two versions)
(definec (A276328 n) (if (zero? n) n (+ 1 (A276328 (- n (A258199 n))))))
(definec (A276328 n) (if (zero? n) n (+ (A276333 n) (A276328 (A276335 n)))))
;; Third version which explicitly searches a minimal representation of n as a sum of terms of A001563 (but please see the comment):
(definec (A276328_by_minimization n) (if (zero? n) n (let loop ((i (A258198 n)) (m #f)) (cond ((zero? i) m) ((not m) (loop (- i 1) (+ 1 (A276328_by_minimization (- n (A001563 i)))))) (else (loop (- i 1) (min m (+ 1 (A276328_by_minimization (- n (A001563 i)))))))))))

Crossrefs

Cf. A001563, A258199.

Cf. A000120, A276329, A276330, A276332, A276333, A276335.

Cf. A276091 (gives all n for which a(n) = A276337(n)).

Cf. also A007895, A034968, A265744, A265745 for similar sequences.

Sequence in context: A027615 A053737 A033924 * A276332 A359264 A274641

Adjacent sequences: A276325 A276326 A276327 * A276329 A276330 A276331

Keyword

nonn,base

Author

Antti Karttunen, Aug 30 2016

Status

approved