login
Luhn algorithm double-and-add sum of digits of n.
16

%I #25 Jul 23 2024 18:05:06

%S 0,1,2,3,4,5,6,7,8,9,2,3,4,5,6,7,8,9,10,11,4,5,6,7,8,9,10,11,12,13,6,

%T 7,8,9,10,11,12,13,14,15,8,9,10,11,12,13,14,15,16,17,1,2,3,4,5,6,7,8,

%U 9,10,3,4,5,6,7,8,9,10,11,12,5,6,7,8,9,10,11,12,13,14,7,8,9,10,11,12,13

%N Luhn algorithm double-and-add sum of digits of n.

%C Starting on the right, sum digits after doubling alternating digits beginning with the second. If doubled digit >9, reduce by 9 (sum of digits).

%C a(n) = A007953(A249873(n)); A093019(n) = 10 - a(10*n) mod 10 if less than 10, otherwise 0. - _Reinhard Zumkeller_, Nov 08 2014

%C First differences are b(n) defined for n>0 as follows. Take the prime factorization of n and let x be the number of 2's, y be the number of 5's, and z be min(x,y). If z is even, b(n) = 1 - 9*z. If z is odd and y=z, b(n) = 2 - 9*z. If z is odd and y>z, b(n) = -7 - 9*z. Now a(n) = a(n-1) + b(n). - _Mathew Englander_, Aug 04 2021

%H Reinhard Zumkeller, <a href="/A093017/b093017.txt">Table of n, a(n) for n = 0..10000</a>

%H John Kilgo, <a href="https://web.archive.org/web/20040627030859/http://www.dotnetjohn.com/articles/articleid97.aspx">Using the Luhn Algorithm</a>, DotNetJohn.com.

%H Webopedia, <a href="http://www.webopedia.com/TERM/L/Luhn_formula.html">Luhn formula</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Luhn_algorithm">Luhn algorithm</a>

%H <a href="/index/De#decimal_expansion">Index entries for sequences related to decimal expansion of n</a>

%F a(0)=0; for n not divisible by 10, a(n)=1+a(n-1); for n divisible by 10 but not 50, a(n)=2+a(n-10); for n divisible by 50 but not 100, a(n)=1+a(n-50); for n divisible by 100, a(n)=a(n/100). - _Mathew Englander_, Aug 04 2021

%e a(18) = 2*1 + 8 = 10.

%e a(59) = (1+0) + 9 = 10 (1 and 0 are the digits in 10 = 2*5).

%o (Haskell)

%o a093017 n = if n == 0 then 0 else a093017 n' + a007953 (2 * t) + d

%o where (n', td) = divMod n 100; (t, d) = divMod td 10

%o -- _Reinhard Zumkeller_, Nov 08 2014

%o (Python)

%o def a(n):

%o s = str(n)

%o r = s[::-1]

%o x = sum(int(d) for d in r[::2])

%o x += sum(q if (q:=2*int(d)) < 10 else q-9 for d in r[1::2])

%o return x

%o print([a(n) for n in range(87)]) # _Michael S. Branicky_, Jul 23 2024

%Y Cf. A093018-A093029.

%Y Cf. A007953, A093019.

%K easy,nonn,base

%O 0,3

%A _Ray Chandler_, Apr 03 2004