| Bytes | Lang | Time | Link |
|---|---|---|---|
| 124 | R | 240812T082555Z | Dominic |
| 018 | 05AB1E | 240812T130802Z | Kevin Cr |
| 080 | JavaScript ES7 | 240809T162406Z | Arnauld |
| 103 | Retina | 240811T000621Z | Neil |
| 018 | Jelly | 240809T183703Z | Unrelate |
| 035 | APLDyalog Unicode | 240810T143509Z | akamayu |
| 041 | Charcoal | 240809T235450Z | Neil |
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
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
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)
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
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
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.
Jelly, 18 bytes
J:g¥Ƭ’}ṪU×ḷb§¥ƬṪS%
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%
ç 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.
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
Charcoal, 41 bytes
¬﹪ΣEθ∧ι⊕﹪⊖×ι⌈Φ⊕Eθμ∧¬﹪⁻Lθκλ⬤…²η∨﹪λν﹪⊖ην⊖ηη
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
E Map over values
ι Current values
∧ Logical And
θ Input array
E Map over values
μ Inner index
⊕ Vectorised increment
Φ Filtered where
θ Input array
L 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.