A109012 a(n) = gcd(n,9).

9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, 1, 3, 1, 1, 9, 1

Offset: 0

Author

Mitch Harris

Keywords

• nonn
• easy
• mult

Comments

Start with positive integer n. At each step, either (a) multiply by any positive integer or (b) remove all zeros from the number. a(n) is the smallest number that can be reached by this process. - David W. Wilson, Nov 01 2005

From Martin Fuller, Jul 09 2007: (Start)

Also the minimal positive difference between numbers whose digit sum is a multiple of n. Proof:

Construction: Pick a positive number that does not end with 9, and has a digit sum n-a(n). To form the lower number, append 9 until the digit sum is a multiple of n. This is always possible since the difference is gcd(n,9). Add a(n) to form the higher number, which will have digit sum n.

E.g., n=12: prefix=18, lower=18999, higher=19002, difference=3.

Minimality: All numbers are a multiple of a(n) if their digit sum is a multiple of n. Hence the minimal difference is at least a(n). (End)

Links

• Antti Karttunen, Table of n, a(n) for n = 0..100000
• Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,0,1).

Crossrefs

Cf. A109004.

Cf. A109007, A109008, A109009, A109010, A109011, A109013, A109014, A109015.

Cf. A074232, A374039.

Programs

Mathematica

GCD[Range[0, 100], 9] (* Paolo Xausa, Aug 28 2024 *)

PARI

a(n)=gcd(n,9) \\ Charles R Greathouse IV, Oct 07 2015

Python

from math import gcd
def a(n): return gcd(n, 9)
print([a(n) for n in range(101)]) # Michael S. Branicky, Sep 01 2021

Formula

a(n) = 1 + 2*[3|n] + 6*[9|n], where [x|y] = 1 when x divides y, 0 otherwise.

a(n) = a(n-9).

Multiplicative with a(p^e, 9) = gcd(p^e, 9). - David W. Wilson, Jun 12 2005

G.f.: (-9 - x - x^2 - 3*x^3 - x^4 - x^5 - 3*x^6 - x^7 - x^8) / ((x-1)*(1 + x + x^2)*(x^6 + x^3 + 1)). - R. J. Mathar, Apr 04 2011

Dirichlet g.f.: (1+2/3^s+6/9^s)*zeta(s). - R. J. Mathar, Apr 04 2011