Generalized Super-Luhn

Question

Background

Luhn's Algorithm is a simple check digit formula used to validate a variety of identification numbers. In standard Luhn, each second digit from the end is doubled, and then the digits of all numbers are summed. If the sum mod 10 is 0, the algorithm passes.

I did some math and found that multiplying by two is not the only method that creates an ordering of the digits. In fact, anything not divisible by a nontrivial divisor of 10 - 1 works.

Your Task

You will be given a base B and a list of numbers less than B representing the digits. Now, for each number N, do the following:

• Let I be the 1-based distance of that number to the end of the list. So the last value would have I = 1, the second-to-last value would have I = 2, etc.

• Let Factor = I / gcd(I, B - 1). Repeat this division by a GCD as necessary to eliminate any common factors, as in the case where B - 1 divides I multiple times. Only numbers co-prime to B - 1 work, so this converts I to the "closest" coprime version.

  In other words, remove any factors that are shared with B - 1.

• Multiply the number N by Factor, then repeatedly sum the digits (in base B) until only one remains.

You should have exactly the same number of digits as the original list. Sum them, and if the result % B is zero, the checksum passes. If it is any other value, it fails.

You may assume that base >= 3 and that the input list is non-empty.

Test Cases

Truthy:

[[1, 4, 1], 12],
[[7, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9], 12],
[[10, 2, 3, 4, 5], 12],
[[10, 2, 3, 4, 8], 11]

Falsy:

[[1, 4, 1, 1], 12],
[[7, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10], 12],
[[10, 2, 3, 4, 5], 11],
[[0, 2, 3, 3, 5], 11]

As this is a decision-problem, you may choose to invert the output if you desire.

Worked Out Example

Starting list: [7, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9], base: 12

The indices with factors shared with 11 removed, shown here in reverse, are:

1   2   3   4   5   6   7   8   9   10  1   12

Then multiplying and taking the digital root, still with the terms shown in reverse:

9   9   5   10  2   3   2   10  5   9   1   7

Finally, the cumulative sums mod 12 are:

9   6   11  9   11  2   4   2   7   4   5   0

The final sum is 0, so this example passes the checksum.

Answer 1

Jelly, 18 bytes

J:g¥Ƭ’}ṪU×ḷb§¥ƬṪS%

Try it online!

A less naive computation of the digital roots comes out a bit longer by having to special-case 0. Inverted output: truthy (nonzero) if the checksum fails.

J                     1-indices from the start
 :                    divided by
  g¥                  their GCDs with
     ’}               B - 1
    Ƭ  Ṫ              repeated while unique,
        U             reversed
         ×ḷ           times each N.
              ƬṪ      Loop while unique:
           b ¥        Convert each to base B
            §         and sum each.
                S     Sum
                 %    mod B.

A version which ties with an alternative to repeated division:

Jelly, 18 bytes

:gɓ’*
JçU×ḷb§¥ƬṪS%

Try it online!

ç is used to save 1 byte compared to an excessive combination of quicks in :g¥*@¥’} or :g¥’*¥@¥:

:        Divide the indices by
 g       their GCDs with
  ɓ’     B - 1
    *    raised to the power of each index.

No prime factor of any index has a multiplicity greater than that index, so it suffices to exponentiate B - 1 that many times.

Answer 2

JavaScript (ES7), 80 bytes

Expects (base)(list). Returns zero for truthy or non-zero for falsy.

(b,i=!b--)=>g=a=>a+a&&(G=(x,y)=>y?G(y,x%y):(a.pop()*i/x-1)%b-~g(a))(++i,b**i)%~b

Try it online!

Method

We divide the indices by their GCDs with \$b-1\$ raised to the power of each index. This trick is borrowed from Unrelated String's answer.

The digital root is computed with the direct formula (from Wikipedia):

$$\operatorname{dr}_b(n)=\begin{cases} 0&\text{if }n=0\\ 1+\big((n-1)\bmod(b-1)\big)&\text{if }n\neq0 \end{cases}$$

Because the sign of % in JS is the sign of the dividend, we actually do not need to handle the \$n=0\$ edge case separately.

Commented

(               // outer function taking:
  b,            //   b = base
  i = !b--      //   i = index, initialized to 0
                //   turn b into b' = b - 1
) =>            //
g = a =>        // g = inner recursive function taking a[]
a + a && (      // if a[] is not empty:
  G = (x, y) => //   G is a recursive function taking (x, y)
  y ?           //   if y is not zero:
    G(y, x % y) //     recursive call with x = y, y = x mod y
  :             //   else:
    (           //     x is now GCD(x, y)
      a.pop()   //     extract the last value from a[]
      * i       //     multiply it by i
      / x       //     divide by x
      - 1       //     subtract 1
    ) % b       //     reduce modulo b'
    - ~g(a)     //     add 1 + the result of a recursive call to g
)(++i, b ** i)  //   increment i and process the initial call to G
                //   with x = i, y = b' ** i
% ~b            // reduce the final result modulo the original base

Answer 3

Charcoal, 41 bytes

¬﹪ΣＥθ∧ι⊕﹪⊖×ι⌈Φ⊕Ｅθμ∧¬﹪⁻Ｌθκλ⬤…²η∨﹪λν﹪⊖ην⊖ηη

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if Luhn, nothing if not. Explanation: Mostly doing recursive GCD without having access to recursion or GCD.

    θ                                       Input array
   Ｅ                                        Map over values
      ι                                     Current values
     ∧                                      Logical And
                θ                           Input array
               Ｅ                            Map over values
                 μ                          Inner index
              ⊕                             Vectorised increment
             Φ                              Filtered where
                       θ                    Input array
                      Ｌ                     Length
                     ⁻                      Subtract
                        κ                   Outer index
                   ¬﹪                       Is divisible by
                         λ                  Inner value
                  ∧                         Logical And
                           …                Range from
                            ²               Literal integer `2`
                             η              To input base
                          ⬤                 All values satisfy
                                 ν          Innermost value
                               ﹪            Does not divide
                                λ           Inner value
                              ∨             Logical Or
                                     ν      Innermost value
                                  ﹪         Does not divide
                                    η       Input base
                                   ⊖        Decremented
            ⌈                               Take the maximum
          ×                                 Multiplied by
           ι                                Current value
         ⊖                                  Decremented
        ﹪                                   Modulo
                                       η    Input base
                                      ⊖     Decremented
       ⊕                                    Incremented
  Σ                                         Take the sum
 ﹪                                          Modulo
                                        η   Input base
¬                                           Is zero
                                            Implicitly print

The recursive GCD of I and B-1 is the highest factor of I that shares no common factor with B-1.

Answer 4

05AB1E, 18 bytes

āRΔDI<¿÷}*ΔIвO}OIÖ

Inputs in the order \$list,B\$.

Try it online or verify all test cases.

Explanation:

ā         # Push a list in the range [1, first (implicit) input-length] (without
          # popping)
 R        # Reverse it to range [length,1]
  Δ       # Loop until the result no longer changes:
   D      #  Duplicate the current list
    I     #  Push the second input-integer B
     <    #  Decrease it by 1
      ¿   #  Get the GCD of each duplicated value with this B-1
       ÷  #  (Integer-)divide the value by its GCD(value,B-1)
  }*      # After the changes-loop: multiply them to the original (unreversed)
          # input-values
    Δ     # Loop again until the result no longer changes:
     Iв   #  Convert each inner value to a base-B list
       O  #  Sum those inner lists together
    }O    # After the second changes-loop: sum the list together
      IÖ  # Check whether it's divisible by the second input B
          # (after which this is output implicitly as result)

Answer 5

APL(Dyalog Unicode), 35 bytes ^SBCS

A dfn that takes B and N as its left and right arguments, respectively. It outputs zero for true instances and non-zero output for false instances.

{⍺|+⌿⍺(+⌿⊥⍣¯1)⍣≡⍵×(⍺-1)(⊢÷∨)⍣≡⌽⍳≢⍵}
                              ⌽⍳≢⍵  ⍝ Reversed indices of N
                  (⍺-1)(⊢÷∨)⍣≡      ⍝ Divided by gcd with B-1 until converges
                ⍵×                  ⍝ Multiplied by N
     ⍺(+⌿⊥⍣¯1)⍣≡                    ⍝ Sum of digits in base B until converges
 ⍺|+⌿                               ⍝ Sum in mod B

Try it on APLgolf!

Answer 6

Retina, 103 bytes

\D
:$<;&$&
\d+
*
+r`:(\3)+(,.*;\3*(__+)_$)
:$#1*_$2
(_*):(_+)
$.1*$2
+`(_+)(?=.*;\1$)
_
,

r`^\1*;(_+)$

Try it online! Takes input as a comma-separated list of integers semicolon-separated from the base but link is to test suite that converts from the test case format for convenience. Explanation:

\D
:$<;&$&

For each value, suffix its reverse 1-based index.

\d+
*

Convert everything to unary.

+r`:(\3)+(,.*;\3*(__+)_$)
:$#1*_$2

Repeatedly reduce all of the indices by GCD with the decremented base.

(_*):(_+)
$.1*$2

Multiply each value by its reduced index.

+`(_+)(?=.*;\1$)
_

Take the digital root of each value.

,

r`^\1*;(_+)$

Check whether the base divides the sum.

Answer 7

R, 148 145 124 bytes

Edit: -3 bytes thanks to pajonk
Edit2: -21 bytes by using simplified digital root algorithm copied from Arnauld's answer

\(l,b,s=sapply)sum(s(rev(l)*s(seq(!l),`?`<-\(x,z=x)`if`(z>1,`if`(x%%z|(b-1)%%z,x?z-1,?x/z),x)),\(x)(1+(x-1)%%(b-1))*!!x))%%b

Attempt This Online!

Returns zero (falsy) for checksum-pass, or a positive inteter (truthy) for a checksum fail.

Ungolfed

# ncd (no common divisors) = funtion that returns x without any common divisors with y
ncd=
n=function(x,y,z=x)`if`(z>1,`if`(x%%z|y%%z,n(x,y,z-1),n(x/z,y)),x)

# digital_root = function that returns digital root of x in given base
digital_root=
function(x,base=10)(1+(x-1)%%(base-1))*!!x

# luhn = uses helper functions ncd & digital root to calculate luhn modulus
luhn=
function(l,b)sum(sapply(rev(l)*sapply(seq(!l),ncd,y=b-1),digital_root,base=b))%%b