12
\$\begingroup\$

Given a message, append checksum digits using prime numbers as weights.


A checksum digit is used as an error-detection method.
Take, for instance, the error-detection method of the EAN-13 code:
The checksum digit is generated by:

  • Multiplying each digit in the message alternating by 1 and 3 (the weights)
  • Summing it up
  • Calculating the difference between the nearest multiple of 10 (Maximum possible value) and the sum

E.g:

1214563 -> 1*1 + 2*3 + 1*1 + 4*3 + 5*1 + 6*3 + 3*1 = 46
50 - 46 = 4

Although the EAN-13 code can detect transposition errors (i.e. when two adjacent bits are switched, the checksum will be different) it can't detect an error when two bits with the same weight are swapped.
E.g.: 163 -> checksum digit 8, 361 -> checkdum digit 8

Using a prime checksum, with the first weight being the first prime number, the second weight being the second prime number, etc., errors can be detected when any two bits are swapped. Because the primes act as weights, you have an extra factor, the length of the message l:

  1. Multiply each digit in the message by the nth prime (First digit times the first prime, second digit times the second prime, etc.)
  2. Sum it up
  3. Calculate the sum of each prime up to the lth prime multiplied by 9 plus 1 (Maximum possible value)
  4. Subtract the second sum by the first sum

E.g.:

1214563 -> 1*2 + 2*3 + 1*5 + 4*7 + 5*11 + 6*13 + 3*17 = 225
9*(2+3+5+7+11+13+17) + 1 -> 523
523 - 225 = 298

Rules

  • Take a decimal string, leading zeros are prohibited
  • Output the checksum digits
  • Standard Loopholes apply
  • This is , the shortest answer wins!

Examples

[In]:  213
[Out]: 69

[In]:  89561
[Out]: 132

[In]:  999999
[Out]: 1

[In]:  532608352
[Out]: 534
\$\endgroup\$
3
  • \$\begingroup\$ If you wanted to use this it seems you'd also need to identify how many of the trailing digits are in the checksum, which would immediately defeat its utility :( \$\endgroup\$ Commented Oct 15, 2022 at 17:49
  • \$\begingroup\$ @JonathanAllan sad. The least you could do is to use 0 as a separator, I guess \$\endgroup\$
    – math scat
    Commented Oct 15, 2022 at 17:51
  • 2
    \$\begingroup\$ Side comment (tongue in cheek): if we're willing to allow multidigit checksums, we can weight the digits by the powers of 10 starting from the rightmost digit ... of course then the "checksum" is just repeating the original number :p \$\endgroup\$ Commented Oct 16, 2022 at 5:40

20 Answers 20

6
\$\begingroup\$

sclin, 26 bytes

_9+""Q $P""zip *0\+ fold1+

Try it here!

I didn't like how my old language lin was turning out, so I've spent a bunch of time reworking/re-implementing it in Scala! So far it's very very WIP, but it works.

For testing purposes (use -i flag if running locally):

[2 1 3].
_9+""Q $P""zip *0\+ fold1+

Explanation

Prettified version:

_ 9+ dup $P () zip * 0 \+ fold 1+

Assuming input digit list x,

  • _ 9+ i.e. -x + 9
  • dup $P () zip truncate infinite list of primes to x's length (more literally, zip x to primes but only keep primes)
  • * (vectorized) multiply
  • 0 \+ fold sum
  • 1+ increment
\$\endgroup\$
5
\$\begingroup\$

Mathematica, 32 29 bytes

(9-#).Prime@Range@Length@#+1&

View it on Wolfram Cloud!

-3 bytes thanks to Roman!

Accepts input as a list of decimal digits.

\$\endgroup\$
2
  • \$\begingroup\$ 29 bytes: (9-#).Prime@Range@Length@#+1& – most Mathematica commands are Listable. \$\endgroup\$
    – Roman
    Commented Oct 16, 2022 at 16:12
  • \$\begingroup\$ @Roman that is very good to know, thanks! \$\endgroup\$
    – hakr14
    Commented Oct 16, 2022 at 16:16
5
\$\begingroup\$

Fig, \$13\log_{256}(96)\approx\$ 10.701 bytes

}S*-x9tFmC@pL

Try it online!

-1 character thanks to Seggan

\$\endgroup\$
1
  • \$\begingroup\$ -1 Fig byte \$\endgroup\$
    – Seggan
    Commented Oct 18, 2022 at 12:33
4
\$\begingroup\$

Vyxal, 8 bytes

Thanks to Steffan for removing the flag!

9ε:ẏǎ*∑›

Try it Online!

Explanation:

9ε:ẏǎ*∑› # whole program

9ε       # absolute of n-9 (vectorized)
  :ẏ     # push range of the list length
    ǎ    #  and convert into primes
     *   # multiplication (vectorized)
      ∑  # sum the result
       › # and increment it
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can use ε instead of - and remove the flag. \$\endgroup\$
    – naffetS
    Commented Oct 15, 2022 at 18:08
3
\$\begingroup\$

Nibbles, 13 bytes (26 nibbles)

+~+!$|,~==,|,$~%@$2~*- 9

Nibbles has no prime number builtins, so 7.5 bytes (15 nibbles) are used here to construct the infinite list of primes:

|,~==,|,$~%@$2  # infinite list of primes:
|               # filter
 ,~             # the infinite list of integers by
      |  ~      #   list of falsy elements of
           @    #   itself
          % $   #   modulo
       ,$       #   1..each integer 
     ,          #   has a length
   ==           #   equal to
             2  #   two

Once this is done, it's another 5.5 bytes (11 nibbles) to subtract each input digit from 9, zip by multiplication with the primes, and add 1 to the sum.

   !$           # zip the input digits 
      LOP       # with the list of primes (see above)
          ~     # using the function
            - 9 #   subtract each digit from 9
           *    #   and multiply by each prime
  +             # now get the sum
+~              # and add 1 

enter image description here

\$\endgroup\$
3
\$\begingroup\$

J, 16 bytes

1+1#.p:@i.@#*9-]

Accepts a list of digits.

Attempt This Online!

1+1#.p:@i.@#*9-]
             9-] NB. 9 - each item of input
     p:@i.@#     NB. list of primes, input length(#)->range 0..n-1(i.)->nth prime(p:)
            *    NB. element-wise multiplication
  1#.            NB. sum¹
1+               NB. increment

See common use 3 for sum¹.

\$\endgroup\$
3
\$\begingroup\$

Ruby -rprime, 74 60 33 bytes

-27 bytes (!) thanks to south

->d{d.zip(Prime).sum{_2.*9-_1}+1}

Attempt This Online!

In Ruby Prime is enumerable so you can zip with the prime numbers without calling Prime.each or .take.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 33 bytes: ->d{d.zip(Prime).sum{_2.*9-_1}+1}. you can accept an array of digits, so thats the biggest save. also, cool flag use there \$\endgroup\$
    – south
    Commented Oct 16, 2022 at 1:19
2
\$\begingroup\$

JavaScript (ES6), 64 bytes

Expects either a string or an array of digit characters.

f=(s,i=n=0)=>s[i]?(P=x=>n%x--?P(x):x?0:9-s[i++])(n++)*n+f(s,i):1

Try it online!

Commented

f = (              // f is a recursive function taking:
  s,               //   s = input string
  i =              //   i = pointer in s
  n = 0            //   n = prime candidate
) =>               //
s[i] ?             // if s[i] is defined:
  ( P = x =>       //   P is a helper recursive function taking
                   //   x = n - 1 and testing whether n is prime
    n % x-- ?      //   if x does not divide n (decrement x afterwards):
      P(x)         //     do recursive calls until it does
    :              //   else:
      x ?          //     if x is not 0:
        0          //       n is composite: return 0
      :            //     else:
        9 - s[i++] //       n is prime: return 9 - s[i] and increment i
  )(n++)           //   initial call to P with x = n, then increment n
  * n              //   multiply the result by n
  + f(s, i)        //   add the result of a recursive call to f
:                  // else:
  1                //   stop the recursion and add 1 to the final result
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 8 bytes

9αā<Ø*O>

Try it online!

Explanation

9αā<Ø*O>
9α        Get the absolute difference between 9 and each item in the list - call this X
  ā       Push [1..length(a)] without popping
   <      Decrement each
    Ø     Push nth (zero-indexed) prime fore ach
     *    Multiply each by the corresponding item in X
      O   Sum
       >  Increment
\$\endgroup\$
2
\$\begingroup\$

Factor + math.primes math.unicode,  48  47 bytes

[ dup length nprimes dup Σ 9 * 1 + -rot v. - ]

Takes input as a sequence of integers (digits).

Try it online!

        ! { 1 2 1 4 5 6 3 }
dup     ! { 1 2 1 4 5 6 3 } { 1 2 1 4 5 6 3 }
length  ! { 1 2 1 4 5 6 3 } 7
nprimes ! { 1 2 1 4 5 6 3 } { 2 3 5 7 11 13 17 }
dup     ! { 1 2 1 4 5 6 3 } { 2 3 5 7 11 13 17 } { 2 3 5 7 11 13 17 }
Σ       ! { 1 2 1 4 5 6 3 } { 2 3 5 7 11 13 17 } 58     (sum)
9       ! { 1 2 1 4 5 6 3 } { 2 3 5 7 11 13 17 } 58 9
*       ! { 1 2 1 4 5 6 3 } { 2 3 5 7 11 13 17 } 522
1       ! { 1 2 1 4 5 6 3 } { 2 3 5 7 11 13 17 } 522 1
+       ! { 1 2 1 4 5 6 3 } { 2 3 5 7 11 13 17 } 523
-rot    ! 523 { 1 2 1 4 5 6 3 } { 2 3 5 7 11 13 17 }
v.      ! 523 225        (dot product)
-       ! 298
\$\endgroup\$
2
\$\begingroup\$

Python 2, 122 bytes

lambda n:sum(map(lambda x,y:(9-x)*y,map(int,n),[i for i in range(2,len(n)**2)if all(i%m for m in range(2,i))][:len(n)]))+1

Try it online!

Accepts a string as input (ex: "12345")

Restructures the checksum equation as sum((9-d)*p)+1, where d is the input as a list of digits and p is a list of the first len(d) primes.

\$\endgroup\$
1
  • \$\begingroup\$ Here is the gist of the call graph for n="12345". \$\endgroup\$
    – Galen
    Commented Oct 19, 2022 at 0:09
2
\$\begingroup\$

Raku, 40 bytes

{1+sum (9 X-.comb)Z*grep &is-prime,^∞}

Try it online!

  • grep &is-prime, ^∞ is an infinite, lazy sequence of prime numbers.
  • 9 X- .comb is a list of nine minus each digit in the input number.
  • Z* zips those sequences together with multiplication.
  • 1 + sum ... adds those products together and adds 1.
\$\endgroup\$
2
\$\begingroup\$

PARI/GP, 27 bytes

a->1+primes(#a)*[9-x|x<-a]~

Attempt This Online!

\$\endgroup\$
2
\$\begingroup\$

C (clang), 99 93 75 bytes

-4 bytes thanks to c--

i,d;f(*t,*r){for(*r=i=1;*t;*r-=(*t++-57)*i)for(d=2;d>1;)for(d=++i;i%--d;);}

Try it online!

Ungolfed and commented

int primecs(char* text) 
{
    // start then result at one
    int result = 1;        

    // first prime number
    int prime = 1;              

    // loop until we get to the end of the string
    while (*text != 0)
    {
        // calculate the next prime number
        int div = 2;
        while (div != 1)
        {
            // set the divisor to the current value of prime
            div = prime;

            // increment prime;
            prime++;

            // loop until mod(prime, div) = 0
            while (prime % div != 0)
                div--;
        }

        // add the results;
        result += (prime * 9) - ((*text - '0') * prime);

        // move to next character
        text++;
    }
    return result;
}
\$\endgroup\$
0
2
\$\begingroup\$

Excel, 148 147 138 bytes

Saved 1 byte thanks to jdt

If anybody has a shorter way to get a list of primes in Excel, I would love to have it.

=LET(s,SEQUENCE(2^10),t,TRANSPOSE(s+1),n,SEQUENCE(LEN(A1)),SUM((9-MID(A1,n,1))*INDEX(FILTER(s,MMULT(-(IF(s>t,MOD(s,t))=0),s+1)=0),n+1))+1)

Excel does not have a built-in for producing a list of the first n primes. About 80 bytes of this solution is just generating that list. The 84 byte formula below outputs the primes up to 1024. Change the 2^10 based on how much memory you have available and you can get a longer list.


Here is the part that creates the list of prime numbers:

=LET(s,SEQUENCE(2^10),t,TRANSPOSE(s+1),FILTER(s,MMULT(-(IF(s>t,MOD(s,t))=0),s+1)=0))

Let's break down that chonker first. After that, the rest is fairly straightforward. Here's the easy bits:

  • s,SEQUENCE(2^10) just makes an array from 1 to 1024.
  • t,TRANSPOSE(s+1) transposes that array and adds 1 to each element.

Now it gets more complicated.

FILTER(s,MMULT(-(IF(s>t,MOD(s,t))=0),s+1)=0)
  • IF(s>t,MOD(s,t)) creates a 2D array that's filled with either the result of MOD(s,t) or, if s<=t, it's just FALSE.
  • -(IF(~)=0) turns that array into a series of TRUE or FALSE. Note that FALSE from the previous step does not equal 0 because it's not considered a number yet. Once we have that T/F table, we use the unary - to convert TRUE to -1 and FALSE to 0.
  • MMULT(-(IF(~)=0),s+1) multiplies that 1/0 matrix with the same values that we see in t. I have to go re-read how MMULT() works every time I use it so I'm not going to try to explain matrix math here because I'm not good at it. Because [magic], the values at all the prime indices will be 0.
    • Note: The magic isn't perfect so the value 1 is also included in that list because, mathematically, it could be prime. However, we have decided to define prime numbers to not include 1. See more over at math.SE. We could remove it from this results list but it costs less bytes to just skip over it later.
  • FILTER(s,MMULT(~)=0) returns all the values from s where the corresponding value in the MMULT() was 0 since those are the primes (and also 1).

Now we have a neat list of all the prime numbers from 1 to 2^10 or whatever value your memory allows.

OK, if we used LET() to rename everything in that FILTER() function to just p (which costs 4 more bytes than not renaming it), then the original function looks like this:

=LET(s,SEQUENCE(2^10),t,TRANSPOSE(s+1),p,FILTER(s,MMULT(-(IF(s>t,MOD(s,t))=0),s+1)=0),n,SEQUENCE(LEN(A1)),SUM((9-MID(A1,n,1))*INDEX(p,n+1))+1)

When we take out the bits we already know about in the formula above, it looks like this:

=LET(s,~,t,~,p,~,n,SEQUENCE(LEN(A1)),SUM((9-MID(A1,n,1))*INDEX(p,n+1))+1)

Here are the last few pieces:

  • n,SEQUENCE(LEN($A1)) creates an array 1 to the length of the input.
  • (9-MID($A1,n,1)) extracts each digit from the input and subtracts it from 9.
  • *INDEX(p,n+1) multiplies that result by the nth term from our prime list (shifted up by 1 to correct for the 1 at the beginning).
  • SUM(~)+1 adds up all those results and adds 1.

Here's the final result:

Final Screenshot

\$\endgroup\$
7
  • 1
    \$\begingroup\$ truly awesome indeed \$\endgroup\$
    – math scat
    Commented Oct 18, 2022 at 15:16
  • \$\begingroup\$ @jdt That inspired me to go find a solution 9 bytes shorter. Surprisingly enough, it's actually a better prime list since it doesn't include the errors at the end. \$\endgroup\$ Commented Oct 18, 2022 at 21:19
  • \$\begingroup\$ Would something like this help with creating a list of primes? =REDUCE("",ROW(1:999),LAMBDA(a,b,a&IF(SUM(0+(MOD(b,SEQUENCE(b))<1))<3,b&",",""))) \$\endgroup\$
    – jdt
    Commented Nov 29, 2022 at 17:46
  • \$\begingroup\$ @jdt That does make a concatenated string of primes but It's not much shorter than the solution above that creates an array. I'm not comfortable with REDUCE or LAMBDA since they're not in my version, but I invite you to flesh it out to a full solution. I'd be interested to see it in action. \$\endgroup\$ Commented Nov 29, 2022 at 18:55
  • 1
    \$\begingroup\$ Invitation accepted :-) =LET(r,ROW(1:99),s,SEQUENCE(LEN(A1)),SUM((9-MID(A1,s,1))*REDUCE(-s,r,LAMBDA(a,b,IFS(SUM(0+(MOD(b,r)<1))>2,a,a<0,a+1,a,a,b,b))))+1) \$\endgroup\$
    – jdt
    Commented Nov 30, 2022 at 14:36
1
\$\begingroup\$

Jelly,  11 10  8 bytes

9_ḋJÆN$‘

A monadic Link that accepts a list of integers and yields the checksum value as an integer.

Try it online!

How?

9_ḋJÆN$‘ - Link: list of integers, A
9        - nine
 _       - subtract A (vectorises) -> Remainders = [9-A1, 9-A2, ...]
      $  - last two links as a monad - f(A):
   J     -   range of length (A) -> [1,2,3,4,5,...,length(A)]
    ÆN   -   nth prime -> Primes = [2,3,5,7,11,...,length(A)th-Prime]
  ḋ      - (Remainders) dot product (Primes) = (9-A1)*2 + (9-A2)*3 + ...
       ‘ - increment -> checksum
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 36 bytes

≔¹η≔¹ζFS«≦⊕ζW⊙…²ζ¬﹪ζλ≦⊕ζ≧⁺×ζ⁻⁹Iιη»Iη

Try it online! Link is to verbose version of code. Explanation:

≔¹η

Start with a checksum of 1.

≔¹ζ

Start looking for prime numbers greater than 1.

FS«

Loop over the input digits as a string.

≦⊕ζ

Increment the candidate prime number.

W⊙…²ζ¬﹪ζλ

While it has a nontrivial proper divisor...

≦⊕ζ

... increment the candidate prime number.

≧⁺×ζ⁻⁹Iιη

Account for the contribution of this digit to the checksum.

»Iη

Output the final checksum.

34 bytes using the newer version of Charcoal on ATO:

≔¹ηW‹LυLθ«≦⊕η¿⬤υ﹪ηκ⊞υη»I⊕Σ×υ⁻⁹I⪪θ¹

Attempt This Online! Link is to verbose version of code. Explanation:

≔¹η

Start looking for prime numbers greater than 1.

W‹LυLθ«

Repeat until sufficient prime numbers have been obtained.

≦⊕η

Increment the candidate prime number.

¿⬤υ﹪ηκ

If it is not evenly divided by any prime number found so far, ...

⊞υη

... add the prime number to the predefined empty list.

»I⊕Σ×υ⁻⁹I⪪θ¹

Calculate the incremented dot product of the list of prime numbers with the digits of the 9's complement of the input number.

\$\endgroup\$
1
\$\begingroup\$

Pyth, 17 bytes

hs*Vm-9vdz.fP_Zlz

Try it online!

Explanation

h                    add one to
 s                   the sum of
  *V                 the vectorized multiplication of
    m-9vdz               9-d where d is each digit of the input
          .fP_Zlz        the first n primes where n is the length of the input

\$\endgroup\$
1
\$\begingroup\$

Python, 116 bytes

Takes input a decimal number as a string, while using a recursive function to calculate the first n primes and the proposed equation of user GotCubes.

f=lambda n,i=1,p=1:n*[0]and p%i*[i]+f(n-p%i,i+1,p*i*i)
c=lambda s:sum(y*(9-x)for x,y in zip(map(int,s),f(len(s))))+1

Attempt This Online!

\$\endgroup\$
1
\$\begingroup\$

GeoGebra, 73 bytes

n={
InputBox(n
l=IterationList(NextPrime(a),a,{2},Length(n)-1
1+Sum(9l-nl

Input is comma separated digits in the Input Box

Try It On GeoGebra!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.