# Tough Problem 3 (Formula)



## pgc01

Hi all

I'm back with one more though problem. As Barry suggested, this is simpler, but still interesting, I hope.


As many of you know, the Luhn algorithm is used in most of the credit and debit cards to validate the number. For ex., with my cards that have 16 digits, given the 15 first digits I could find the 16th.

You have a brief explanation of the algorithm used here (look especially at the example for the number 49927398716):

Luhn algorithm - Wikipedia


*Problem:*

Given the 15 first digits of a credit/debit card, calculate the 16th.


Rules:

- if possible one formula

- better if the algorithm works also for numbers that don't have 15 digits (like the Wiki example)

- MVPs and experienced users please wait 12 hours before posting to allow others to have some fun.

(- No search the web for a solution, it will spoil the fun)


Remark: you can try the solution with your own cards

I post some solutions. The 4th doesn't have 15 digits.

Book5.xlsmAB1123456789012345221292782347623546398765432109876584549927398716Sheet2


----------



## pgc01

Hi again

I thought that instead of just posting the link it would be easier if I would post a brief explanation of the Luhn algorithm.

Let's consider a possible credit card number:

1234567890123452

The Luhn Algorithm is very simple.

Consider the digits ordered form right to left.

Multiply by 2 all the digits in even positions

(5*2) (3*2) (1*2) (9*2) (7*2) (5*2) (3*2) (1*2)

Add all the digits in odd positions with the digits of the double of the numbers in even positions, that we calculated before.

2 + (1+0) + 4 + (6) + 2 + (1) + 0 + (1+8) + 8 + (1+4) + 6 + (1+0) + 4 + (6) + 2 + (1)

The result is 60

Since the result is a multiple of 10, the number is valid.


----------



## schielrn

hmmm... I cannot come to the correct answer for rows 2 and 3, but I match the answers for the wikipedia article and 1 and 4, so I must be missing something because it doesn't even work on my own credit card. I can't wait to see some of the answers because mine is far from elegant.


----------



## schielrn

Ok, I think I took the wikipedia article the wrong way?  Aren't you suppose to for row 1 add 1 & 6 to add to 7? and not use 16 in the sum?  Maybe I misread something.  If that is the case, could the last number also be 3, since that would then sum to 120?


----------



## pgc01

Hi schielrn

I'm glad you looked into this so soon. You are absolutely right. I have looked at this at the beginning of the week and now I messed up. I'll ask a moderator to correct my second post.

As the Wikipedia article says, you are right, you have to add the digits of the double of the numbers in even positions from the right.

My examples are right, just my explanation wasn't.

Can I ask you to confirm the examples in rows 2 and 3?

Book5.xlsmABCDEFGHIJKLM1DigitEven *2Add DigitsDigitEven *2Add Digits2129278234762354016669876543210987650188832488251014355536665436647145652225888766123691898777770009848881221093339222111024410366121188811444131271451251011413222136661514918914714516152221588817161221691891819Sum80Sum80Sheet2


----------



## Ron Coderre

pgc01 said:


> Hi schielrn
> 
> Can I ask you to confirm the examples in rows 2 and 3?


 
I'm not schielrn...but, I checked your examples. They're all correct.


----------



## pgc01

Thank you Ron. 

I'll be waiting for your formula, but you are in the category of those that can only post in a few hours, not to spoil the fun.


----------



## pgc01

P. S.

I didn't write it in the first post, but since many of us still don't have excel 2007, I'd prefer a formula that works also in previous versions.


----------



## yytsunamiyy

I don't have a formula solution to your problem pgc - great idea by the way  - but in an earlier thread of mine I applied myself to checking the validity of CC.

here is the VBA-solution for the Luhn algorythm I came up with, maybe it helps those that have the time to find a solution for this problem 



		Code:
__


CardValidation:
    
     For i = 1 To Len(wert) '-------read digits in Cardnumber
         CheckNr(i) = VBA.Mid(Me.TextBoxCardNr2.Value, i, 1)
     Next i
     
     For j = Len(wert) - 1 To 1 Step -2 '----double alternate digits starting with right - 1
         CheckNr(j) = CheckNr(j) * 2
         If CheckNr(j) > 8 Then ' if doubled is 2-digit number calculate Sum of digits
             CheckString = CheckNr(j)
             CheckPart(1) = VBA.Left(CheckString, 1)
             CheckPart(2) = VBA.Right(CheckString, 1)
             CheckNr(j) = CheckPart(1) + CheckPart(2)
         End If
     Next j
     
     '------add all CheckNr's to make CheckSum
     For k = 1 To Len(wert)
         CheckSum = CheckSum + CheckNr(k)
     Next k
     
     '------check that Checksum / 10 does not leave remainder - if so CardNr is invalid
     If Not CheckSum Mod 10 = 0 Then
         GoTo ErrorMsgCardInvalid
     Else
        'more stuff
     End If


If anyone wants to see the whole thread - here its is.


----------



## pgc01

Hi yytsunamiyy

Thank you for posting. Although your solution is not considered for this problem, because we want a formula solution, it's very helpful, since it works and helps anyone that is thinking about which algorithm to use.

If you prefer a vba problem I'll be posting one in the next days. Although a classic, it may be fun to revisit.

Cheers


----------



## Peter_SSs

The previous problems have seemed too difficult for me, but I think I can have a go at this one and the requisite 12 hours has passed with no takers so I'll kick this one off.

Not sure if this works in all cases but seems to for the samples given and for my own card.

Excel WorkbookABC11234567890123452212927823476235463987654321098765845499273987166Tough Problem 3


----------



## yytsunamiyy

pgc01 said:


> Hi yytsunamiyy
> 
> Thank you for posting. Although your solution is not considered for this problem, because we want a formula solution, it's very helpful, since it works and helps anyone that is thinking about which algorithm to use.
> 
> If you prefer a vba problem I'll be posting one in the next days. Although a classic, it may be fun to revisit.
> 
> Cheers



I am the first to admit that formulas are not my forte 
I wasn't trying to post a solution to the problem, I was just thinking that a working Luhn algorythm might help explain the concept further (or maybe just confuse people and send them down the wrong track...). I'm looking forward to seeing the formula solutions.

regards,

Stephan


----------



## fairwinds

Hi,

=10-right(sumproduct(--mid(text(mid(text(a1,rept(0,15)),row(indirect("1:15")),1)*{2;1;2;1;2;1;2;1;2;1;2;1;2;1;2},"00"),{1,2},1)))


----------



## Peter_SSs

fairwinds said:


> Hi,
> 
> =10-right(sumproduct(--mid(text(mid(text(a1,rept(0,15)),row(indirect("1:15")),1)*{2;1;2;1;2;1;2;1;2;1;2;1;2;1;2},"00"),{1,2},1)))


G'day fairwinds

Much shorter than mine and still will be when you do what I think is a required final tweak. For ...
123456789012346
... you formula returns 10, when I believe it should be 0. It's a similar problem I had to deal with when finalising my attempt.


----------



## fairwinds

Right. Let's wrap it in Right()  maybe with also a coercer if needed.

=RIGHT(10-RIGHT(SUMPRODUCT(--MID(TEXT(MID(TEXT(A1,REPT(0,15)),ROW(INDIRECT("1:15")),1)*{2;1;2;1;2;1;2;1;2;1;2;1;2;1;2},"00"),{1,2},1))))


----------



## barry houdini

That's certainly better than anything I came up with, fairwinds......but perhaps use MOD instead of two RIGHTs, i.e.

=MOD(SUMPRODUCT(-MID(TEXT(MID(TEXT(A1,REPT(0,15)),ROW(INDIRECT("1:15")),1)*{2;1;2;1;2;1;2;1;2;1;2;1;2;1;2},"00"),{1,2},1)),10)


----------



## pgc01

Hi

Peter

Welcome. I tested your formula with 15 digit codes and it works ok.

Fairwinds, Barry

Both formulas before and after Barry's modifications are ok for 15 digit codes.


I'll be waiting for the formulas that work independently from the number of digits.



> - better if the algorithm works also for numbers that don't have 15 digits


 
As I wrote in my first post, the formula should preferably be independent from the number of digits.

I honestly don't know how many digits we should consider. I already knew that some codes with 20 digits used Luhn's algorithm. Today I came accross some codes in the European Banking system that use 23 digits.

Since I don't know what's the maximum number of digits that makes sense, let's be reasonable and consider, for ex., a maximum of 99 digits.

Cheers


----------



## barry houdini

Hello pgc,

My first attempt, before I saw Peter's and fairwinds' suggestions, was this formula which should deal with any number of digits from 1 to 99 (and more)

=MOD(LEN(SUBSTITUTE(A1,0,""))-LEN(A1)-SUMPRODUCT((MOD(MID(A1,ROW(INDIRECT("1:"&LEN(A1))),1)*(MOD(ROW(INDIRECT("1:"&LEN(A1)))+LEN(A1)+1,2)+1)-1,9)+1)),10)

...or  an amalgam of fairwinds' version and the above.....

=MOD(SUMPRODUCT(-MID(TEXT(MID(A1,ROW(INDIRECT("1:"&LEN(A1))),1)*(MOD(ROW(INDIRECT("1:"&LEN(A1)))+LEN(A1)+1,2)+1),"00"),{1,2},1)),10)


----------



## pgc01

Hi all

I think we can all agree that we have solutions of the best quality in this thread. I consider the last formula posted by Barry, the "an amalgam of Fairwinds' version and the above" formula really great.

I had posted an answer to this problem about 2 years ago, here:

http://www.mrexcel.com/forum/showthread.php?p=1190595

One thing interesting in that thread is that after the formula for a code with digits, we continue with an extension for alphanumeric codes. That was my first option for this problem, before I opted for digits only.

Any formula posted here was much better than mine, that was longer and array entered. This is one good point of these threads, you end up learning new and better approaches to the problems.

I'm really happy with the results so far, although I'd like to have more participation, which I hope we'll have in the next problems.


I'll try to post the next Tough Problem (VBA) in the next couple of hours.


I'm very happy to annouce that the next Tough Problem (Formula) will be posted by Barry in the next couple of days. This means that I can also participate! 

Cheers


----------



## schielrn

This is what I have, but when I was evaluating it seemed to be handling all the numbers correctly, but haven't been able to get back to it since Friday.  And also it gives me #Value error in pre-2007, so I can't work on it from home:

=10-MOD(SUMPRODUCT(--(MID(A2,ROW(INDIRECT("1:"&LEN(A2))),1)),--(ISEVEN(ROW(INDIRECT("1:"&LEN(A2))))))*2-SUMPRODUCT(--((MID(A2,ROW(INDIRECT("1:"&LEN(A2))),1))*(ISEVEN(ROW(INDIRECT("1:"&LEN(A2))))*2)>9))*9+SUMPRODUCT(--(MID(A2,ROW(INDIRECT("1:"&LEN(A2))),1)),--(ISODD(ROW(INDIRECT("1:"&LEN(A2)))))),10)

Let me know of any pointers or help you can give me for this?


----------



## barry houdini

Hello schielrn,

I think the problem you have is that ISODD and ISEVEN functions don't work with ranges or arrays, they'll only evaluate single cells, even in 2007.

You probably need to use MOD function with a divisor of 2. If the result is zero then it's even, if 1 it's odd.......


----------



## pgc01

I had not tested it yet, but IsEven() and IsOdd() in excel 2007 seem to work ok with arrays, but not directly with a range with more than 1 cell. In that case, it seems we have to first convert it to an array, like:

=SUMPRODUCT(--ISEVEN({1,2,4})) , array OK

=SUMPRODUCT(--ISEVEN(A1:C1)) , Error, range with more than 1 cell

=SUMPRODUCT(--ISEVEN(A1:C1+0)) , OK, range converted into an array


In your case, Schielrn, however, as Barry wrote you can use neither, if the solution is to work in versions previous to xl2007.


----------



## barry houdini

Thanks for the correction, Pedro. I was a little lazy really, I only tested in Excel 2007 with a range and assumed it wouldn't work with an array either.....how wrong I was


----------



## bertrand_emerit

Hello,
10 years after, some small tweaks :

parsing right-to-left eases the mod() construct
use of round(mod(n,9.5)) gives what we expect for the algorithm : 0 to 9 when n <= 9 and [0.5->]1 to [8.5->]9 when n >= 10
All this sums up to:
=MOD(SUMPRODUCT(-ROUND(MOD(MID(A1,LEN(A1)-ROW(INDIRECT("1:"&LEN(A1)))+1,1)*(MOD(ROW(INDIRECT("1:"&LEN(A1))),2)+1),9.5),0)),10)


----------



## Peter_SSs

bertrand_emerit said:


> 10 years after, some small tweaks :


.. or with the advent of the dynamic array functions in Excel 365, a non-volatile adaptation.

=MOD(-SUM(ROUND(MOD(MID(A2,SEQUENCE(,LEN(A2),LEN(A2),-1),1)*(1+MOD(SEQUENCE(,LEN(A2)),2)),9.5),0)),10)


----------

