• Hi All

    Please note that at the Chandoo.org Forums there is Zero Tolerance to Spam

    Post Spam and you Will Be Deleted as a User

    Hui...

  • When starting a new post, to receive a quicker and more targeted answer, Please include a sample file in the initial post.

Formula Challenge 023 - IMEI Luhn Check

iferror

Member
Hi all,
new to the board but been lurking around for quite some time...and this is the section i love most!

I know i'm probably just going to tickle you a little bit, this is a fairly easy challenge, but nevertheless i'd like to know if there's an alternative solution to the problem at hand.

I'm pretty sure you know what an IMEI is. The structure of the IMEI is as follows: AA-BBBBBB-CCCCCC-D

AA-BBBBBB - is known as Type Allocation Code
CCCCC - represents the serial number
D- is the Luhn check digit for the IMEI

The Luhn algorithm is applied to the first 14 digits of the IMEI and returns only one digit (the last one of the IMEI).
To get the Luhn check digit you have to:
- double every other digit
- sum all the digits
- 10 - (mod(sum;10))

i.e.
IMEI:
12345678901234?
-double every other digit -->
1(4)3(8)5(12)7(16)9(0)1(4)3(8)
- sum all the digits -->
1+(4)+3+(8)+5+(1+2)+7+(1+6)+9+(0)+1+(4)+3+(8) = 63
- 10 - (mod(sum;10)) -->
10-3=7

so ? is 7

The challenge is:
write a single formula that, given an IMEI, would check the last digit and return either TRUE or FALSE according to Luhn Check

So
A1=123456789012349 --> =formula(A1) --> FALSE
whereas
A1=123456789012347 --> =formula(A1) --> TRUE

Looking forward to be amazed by any solution you may come up to.
 

Hui

Excel Ninja
Staff member
I'll start:
= 10-MOD(SUMPRODUCT(LEFT(MID(A1,ROW(OFFSET($A$1,,,LEN(A1))),1)*(IF(ISEVEN(ROW(OFFSET($A$1,,,LEN(A1)))),2,1)),1)+IF(LEN(MID(A1,ROW(OFFSET($A$1,,,LEN(A1))),1)*(IF(ISEVEN(ROW(OFFSET($A$1,,,LEN(A1)))),2,1)))>1,RIGHT(MID(A1,ROW(OFFSET($A$1,,,LEN(A1))),1)*(IF(ISEVEN(ROW(OFFSET($A$1,,,LEN(A1)))),2,1)),1),0)),10) Ctrl+Shift+Enter

= 7


In the above formula $A$1 is fixed
A1 can be changed to the cell which has your value
 
Last edited:

Hui

Excel Ninja
Staff member
If I use a Named Formula
Tmp: =ROW(OFFSET(Sheet1!$A$1,,,LEN(A1)))
It shortens to: =10-MOD(SUMPRODUCT(LEFT(MID(A1,Tmp,1)*(IF(ISEVEN(Tmp),2,1)),1)+IF(LEN(MID(A1,Tmp,1)*(IF(ISEVEN(Tmp),2,1)))>1,RIGHT(MID(A1,Tmp,1)*(IF(ISEVEN(Tmp),2,1)),1),0)),10) Ctrl+Shift+Enter
 

iferror

Member
Nice one!! 5 character shorter than mine!...and you made it even more 'general' as the IMEI can be any lenght (it actually has a fixed lenght of 14+1 char)
 

iferror

Member
Hang on...your formula returns the last digit, the Luhn Checksum digit.
I want a formula that check if the IMEI is correct (thus checking if the Luhn checksum is equal to the last digit)

:)
 

Hui

Excel Ninja
Staff member
My misread of the question

This will do it for you:
=RIGHT(A1,1)=TEXT((10-MOD(SUMPRODUCT(LEFT(MID(LEFT(A1,LEN(A1)-1),ROW(OFFSET($A$1,,,LEN(A1)-1)),1)*(IF(ISEVEN(ROW(OFFSET($A$1,,,LEN(A1)-1))),2,1)),1)+IF(LEN(MID(LEFT(A1,LEN(A1)-1),ROW(OFFSET($A$1,,,LEN(A1)-1)),1)*(IF(ISEVEN(ROW(OFFSET($A$1,,,LEN(A1)-1))),2,1)))>1,RIGHT(MID(LEFT(A1,LEN(A1)-1),ROW(OFFSET($A$1,,,LEN(A1)-1)),1)*(IF(ISEVEN(ROW(OFFSET($A$1,,,LEN(A1)-1))),2,1)),1),0)),10)),"0") Ctrl+Shift+Enter
 

Hui

Excel Ninja
Staff member
With the Named Formula
Tmp: =ROW(OFFSET(Sheet1!$A$1,,,LEN($A$1)-1))
=RIGHT(A1,1)=TEXT(10-MOD(SUMPRODUCT(LEFT(MID(A1,Tmp,1)*(IF(ISEVEN(Tmp),2,1)),1)+IF(LEN(MID(A1,Tmp,1)*(IF(ISEVEN(Tmp),2,1)))>1,RIGHT(MID(A1,Tmp,1)*(IF(ISEVEN(Tmp),2,1)),1),0)),10),"0") Ctrl+Shift+Enter
 

iferror

Member
This is my 253 characters formula
Code:
MOD(
SUM(
IF(
IF(MOD(ROW($A$1:$A$15);2);1*MID(G1;16-ROW($A$1:$A$15);1);2*MID(G1;16-ROW($A$1:$A$15);1))>9;
IF(MOD(ROW($A$1:$A$15);2);1*MID(G1;16-ROW($A$1:$A$15);1);2*MID(G1;16-ROW($A$1:$A$15);1))-9;
IF(MOD(ROW($A$1:$A$15);2);1*MID(G1;16-ROW($A$1:$A$15);1);2*MID(G1;16-ROW($A$1:$A$15);1))
)
);10
)=0
Hui, your formula is 388 characters as it is, but it can be shorthened by assuming a constant IMEI length
 

Somendra Misra

Excel Ninja
Hi,

Well my version is considering IMEI number to be 15 digit.

=RIGHT(A3,1)+0=10-MOD(SUMPRODUCT(INT(2*(MID(A3,2*ROW($1:$7),1)+0)/10)+MOD(2*(MID(A3,2*ROW($1:$7),1)+0),10)+(MID(A3,(2*ROW($1:$7))-1,1)+0)),10)

Regards,
 

iferror

Member
Brilliant!! Neat!! I really like your solution Debraj.

Anyone brave enought to challenge Debaj for something shorther that that??? :)
 

Lori

Active Member
You sure that's what you get with your settings? I'm getting the opposite boolean values for your two examples with both formulas and find they agree with other formulas. Two top most notable members on this site suggest at least the first one is working for them.

I haven't checked that thoroughly and there may well be an error on my part somewhere. There are also numerous other reasons why formulas might appear to give different values for different users. Regional settings changing the meaning of any of the following characters [;][,][\][/], hidden characters in cells such as non-breaking space, html translations when copying, etc. (I have a hunch it may be to do with European settings because of the semicolon used as argument separator in the question.)

Additionally, I think there's a tweak to be made to the problem specification since using "10-mod(sum;10)" for the checksum you can't match a sum that ends with 0. My interpretation was based on http://en.wikipedia.org/wiki/Luhn_check. If this is the case, then other formulas ending 10-RIGHT(A1) could be changed to MOD(-RIGHT(A1),10) or adapted to something like =MOD(...+RIGHT(A1),10)=0.
 
Last edited:

iferror

Member
As the forula does not yeld any error i believe i've already changed , and ; appropriatelly. So no problem there. But what do / and \ stand for?? And yes, you're right, i have European settings.

Can you please explain how the formula works? I tried breaking it down to smaller pieces but couldn't figure out. It may be due to the fact that on my worksheet i receive wrong output.

Thanks ;)

Nice work by the way :)
 

NARAYANK991

Excel Ninja
Hi ,

The formula is almost a work of art ! There are at least 3 or 4 strokes of genius there :

1. Adding the 0 - it does nothing to the calculations , but it is absolutely essential for the technique to work.

2. The usage {1,2,3,4}+{0;4;8;12} ; what this does is generate the numbers 1 through 16 ! It does not matter that they are generated in the form of a matrix , since the MID function does not mind.

3. The usage of the text format for the TEXT function "0 0\/1" ; what this does is interpret the numbers as fractions ! Since the denominator is 1 , it does not matter , but look at what it does ; enter 1 2/1 ( or =1 2/1 ) in a cell and see what Excel displays.

4. The negation of the TEXT function ; this does two things in one stroke ; it converts the text value into a numeric value for the SUM function ; at the same time , since the formula finally does 10 - MOD(sum,10) , this is the same as MOD(-sum,10) ; of course this is not true when MOD(sum,10) is 0 , but in this case , since we are talking of only one digit , and the digit being 0 , this is true !

Narayan
 

Somendra Misra

Excel Ninja
Hi All,

Just for fun, check below the calculation timings of all formulas. Unfortunately I could not make Hui's formula to work.

Number Hui Formula iferror Self Debraj Lori 1 Lori 2
123456789012347
#VALUE!
TRUE
TRUE
TRUE
TRUE
TRUE
Time 1 0.00149 0.00133 0.00125 0.00159 0.00151
0.0015

Time 2 0.00145 0.00134 0.00125 0.00154 0.00151
0.0015

Time 3 0.00149 0.00138 0.00124 0.00153 0.00154
0.00152

Average 0.001476667 0.00135 0.001247 0.001553 0.00152 0.001506667

Regards,
 

Attachments

Lori

Active Member
@iferror @Somendra Misra
Hi!
May I add that shorter neither necessarily means easier nor simpler nor more usable?
Regards!
Very true @SirJB7 - i'd be the first to admit that. But it can be fun to think up ways to do it! (@NARAYANK991 gave a great explanation but it's really just a couple of tricks not art.) Fwiw, I think the shortest would be to combine the two methods above and use the 4x4 matrix method in the second formula which would save 1 character.

In terms of speed it is interesting @Misra's method is quickest. It might be an idea to also consider using {1;2;3;4;5;6;7} for ROW($1:$7) even if it adds a few characters because it removes calculation dependencies and sensitivity to operations like deleting / adding rows.

But for me the formula of @Debraj is the easiest one to follow (and a small modification for a sum ending in zero could be added for completeness.)

Finally, thanks to @iferror for a great challenge!
 
Top