Formula Challenge 006 - What's the largest number you can confirm is a prime?

jeffreyweir · Jul 5, 2013

Challenge Name

What's the largest number you can confirm is a prime?

Challenge Description

1. Write the shortest formula you can to find the largest prime number you can

2. This is a formula challenge. As such, only formula submissions are accepted.

3. There's a handy prime number checker/generator at http://www.numberempire.com/primenumbers.php

Sample Data

Try your formula out on these numbers:

1099513724917

1099513724941

...and whatever other primes you can think of.

Hui · Jul 5, 2013

There are two posts on Prime Numbers right here:

http://chandoo.org/wp/2009/05/29/array-formula-to-check-if-a-number-is-prime-just-for-fun/

http://chandoo.org/wp/2012/07/12/formula-forensics-024/

jeffreyweir · Jul 5, 2013

Yep. Try them out on the sample data.

Luke M · Jul 15, 2013

Very clever Jeff, using numbers that large. Previous discussed methods use ROW function to generate numbers, but the sample data is too large a number to handle. Hmm...

For notes, not a solution:

Using that website, the largest possible prime you can find in XL is 999,999,999,999,989 due to the significant digit limit within XL. Thus, we need to find someway to test divisors between 1 and 31,622,776

Now to try and figure out how to do just that...

shrivallabha · Jul 15, 2013

Maybe a bit offtrack but try the following formula for both numbers posted by JW:

=SQRT(A1)

and check the results.

Luke M · Jul 15, 2013

@shrivallabha

[pre]

Code:

First line shows formula being used
Number	        =SQRT(A2)	=B2^2
1099513724917	1048577	        1,099,513,724,917
1099513724941	1048577	        1,099,513,724,941
Now that's weird. Realizing that there must be some very tiny decimals, modified to this:

Number	        =MOD(SQRT(A2),1)
1099513724917	0.99999427795410100000
1099513724941	0.00000572204589843750

[/pre]
And now I see what's going on.

Luke M · Jul 15, 2013

Given enough calculation power and ignoring the significant digit limit, I think this is formula would work:

--NOT A LEGITIMATE SOLUTION--

=SUMPRODUCT((ROW(A:A)+((COLUMN(1:1)-1)*ROWS(A:A))<=INT(SQRT(A2)))*(MOD(A2,ROW(A:A)+((COLUMN(1:1)-1)*ROWS(A:A)))=0))=1

Running into a problem too with handling very small numbers simultaneously with very large numbers. Continuing to work...

jeffreyweir · Jul 15, 2013

Good to see you guys are on the case.

Couple of pointers

1. http://excel.tips.net/T003302_Large_Numbers_in_the_MOD_Function.html says the MOD function returns an error if the divisor (the second argument in the MOD function), multiplied by 134,217,728, is less than or equal to the number being evaluated (the first argument in the MOD function).

Interestingly that site says the bug has been fixed in Excel 2010, but it looks like it still fails, but at bigger numbers. MOD(2251799999999,2) works, but anything larger fails.

2. I managed to get my formula to check 122,816,065,582,079 before I got the dreaded 'Excel ran out of resources' error.

Luke M · Jul 15, 2013

Here's what I came up with:

=IF(A2<134217728,

SUMPRODUCT((ROW(A:A)+((COLUMN(A1:J1)-1)*ROWS(A:A))<=INT(SQRT(A2)))*(MOD(A2,ROW(A:A)+((COLUMN(A1:J1)-1)*ROWS(A:A)))=0))=1,

SUMPRODUCT((ROW(A:A)+((COLUMN(QCO1:QCX1))*ROWS(A:A))<=INT(SQRT(A2)))*(MOD(A2,ROW(A:A)+((COLUMN(QCO1:QCX1))*ROWS(A:A)))=0))=0)

Which can test numbers up to:

133,040,906,960,896

Largest prime found:

133,040,906,960,893

Excellent challenge JW!

jeffreyweir · Jul 16, 2013

Good stuff. On a more powerful desktop (as opposed to my laptop) I've managed to test this number successfully:

202005700000123

My formula is 347 characters long, so a bit longer than your 265-long one. I think this can still be streamlined somewhat.

Question...what's the hard limit you seem to be avoiding with IF(A2<134217728...?

Luke M · Jul 16, 2013

The MOD limit you mentioned above:

http://chandoo.org/forums/topic/formula-challenge-006-whats-the-number-you-can-confirm-is-a-prime-or-not#post-123502

I at first was going to use MOD for first set of numbers, then the alternative n-d*INT(n/d) setup, when I realized that I could break up the groups of divisors if I know how big the number is. I'm thinking I could further partition the number into smaller segments to reach the ultimate (in XL) of 999,999,999,999,989

Side note: Formula takes so much of my machine's power, I only have 1 formula in entire workbook. Thus, I have not fully tested formula to confirm it's correct. =/

EDIT: Sadly, I've dis-proven my own formula. back to the drawing board for me.

jeffreyweir · Jul 16, 2013

Crikey, Luke...that's a really slow calculating formula on account of those entire row references.

What prime did it fail on?

Also, check out this template, that lets you turn calculation of individual formulas on or off.

https://www.dropbox.com/s/ccyyu2ml6g71o1p/What%27s%20the%20largest%20prime%20number%20you%20can%20find_Jeff%20Weir%20template.xlsm

You put your prime in the cell labled Base Number, and turn Calculate to True for the number you want to calculate. And you can check to see if it gives false positives by putting something in the "Add this to base" cell or clicking on the spin button.

Luke M · Jul 16, 2013

Not even a prime, it registered: 1099513724918

as prime (which clearly isn't. I think I got messed up in my methodology...I was thinking that once I knew that the number x's square was bigger than y, I only need to check divisors between x and y. But now that I think about that more, it's not right. My current workbook is a mess of a scratchpad with notes all over the place. Starting to look like something out of John Nash's scribblings. =P

Not giving up yet, this is exactly the kind of challenge I love.

End of day two, attempted to break up sets of divisors. Monster equation below (DOES NOT WORK)

[pre]

Code:

=IF(SUMPRODUCT((ROW(A:A)+((COLUMN(A1:F1)-1)*ROWS(A:A))&#60;=INT(SQRT(J6)))*((J6-(ROW(A:A)+((COLUMN(A1:F1)-1)*ROWS(A:A)))*INT(J6/(ROW(A:A)+((COLUMN(A1:F1)-1)*ROWS(A:A)))))=0))=1,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(G1:L1)-1)*ROWS(A:A))&#60;=INT(SQRT(J6)))*((J6-(ROW(A:A)+((COLUMN(G1:L1)-1)*ROWS(A:A)))*INT(J6/(ROW(A:A)+((COLUMN(G1:L1)-1)*ROWS(A:A)))))=0))=0,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(M1:R1)-1)*ROWS(A:A))&#60;=INT(SQRT(J6)))*((J6-(ROW(A:A)+((COLUMN(M1:R1)-1)*ROWS(A:A)))*INT(J6/(ROW(A:A)+((COLUMN(M1:R1)-1)*ROWS(A:A)))))=0))=0,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(S1:X1)-1)*ROWS(A:A))&#60;=INT(SQRT(J6)))*((J6-(ROW(A:A)+((COLUMN(S1:X1)-1)*ROWS(A:A)))*INT(J6/(ROW(A:A)+((COLUMN(S1:X1)-1)*ROWS(A:A)))))=0))=0,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(Y1:AD1)-1)*ROWS(A:A))&#60;=INT(SQRT(J6)))*((J6-(ROW(A:A)+((COLUMN(Y1:AD1)-1)*ROWS(A:A)))*INT(J6/(ROW(A:A)+((COLUMN(Y1:AD1)-1)*ROWS(A:A)))))=0))=0,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(AE1:AJ1)-1)*ROWS(A:A))&#60;=INT(SQRT(J6)))*((J6-(ROW(A:A)+((COLUMN(AE1:AJ1)-1)*ROWS(A:A)))*INT(J6/(ROW(A:A)+((COLUMN(AE1:AJ1)-1)*ROWS(A:A)))))=0))=0,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(AK1:AP1)-1)*ROWS(A:A))&#60;=INT(SQRT(J6)))*((J6-(ROW(A:A)+((COLUMN(AK1:AP1)-1)*ROWS(A:A)))*INT(J6/(ROW(A:A)+((COLUMN(AK1:AP1)-1)*ROWS(A:A)))))=0))=0,TRUE,FALSE)))))))

[/pre]

jeffreyweir · Jul 16, 2013

"John Nash' Scribblings". Ha! A Beautiful Formula. Priceless.

Luke M · Jul 17, 2013

Bazinga!

After removing every other formula in my workbook, this formula was able to function, and more importantly, confirm that

999,999,999,999,989 is prime =)

Code:

=IF(SUMPRODUCT((ROW(A:A)+((COLUMN(A:F)-1)*ROWS(A:A))<=INT(SQRT(A2)))*((A2-(ROW(A:A)+((COLUMN(A:F)-1)*ROWS(A:A)))*INT(A2/(ROW(A:A)+((COLUMN(A:F)-1)*ROWS(A:A)))))=0))=1,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(G:L)-1)*ROWS(A:A))<=INT(SQRT(A2)))*((A2-(ROW(A:A)+((COLUMN(G:L)-1)*ROWS(A:A)))*INT(A2/(ROW(A:A)+((COLUMN(G:L)-1)*ROWS(A:A)))))=0))=0,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(M:R)-1)*ROWS(A:A))<=INT(SQRT(A2)))*((A2-(ROW(A:A)+((COLUMN(M:R)-1)*ROWS(A:A)))*INT(A2/(ROW(A:A)+((COLUMN(M:R)-1)*ROWS(A:A)))))=0))=0,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(S:X)-1)*ROWS(A:A))<=INT(SQRT(A2)))*((A2-(ROW(A:A)+((COLUMN(S:X)-1)*ROWS(A:A)))*INT(A2/(ROW(A:A)+((COLUMN(S:X)-1)*ROWS(A:A)))))=0))=0,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(Y:AD)-1)*ROWS(A:A))<=INT(SQRT(A2)))*((A2-(ROW(A:A)+((COLUMN(Y:AD)-1)*ROWS(A:A)))*INT(A2/(ROW(A:A)+((COLUMN(Y:AD)-1)*ROWS(A:A)))))=0))=0,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(AE1)-1)*ROWS(A:A))<=INT(SQRT(A2)))*((A2-(ROW(A:A)+((COLUMN(AE1)-1)*ROWS(A:A)))*INT(A2/(ROW(A:A)+((COLUMN(AE1)-1)*ROWS(A:A)))))=0))=0,TRUE,FALSE))))))

There's certainly ways you could reduce this down by changing ranges, but it works, and after 3 days, my brain is fried. =P

Luke M · Jul 17, 2013

And at 1063 characters, that's probably the longest formula I've written. Thank goodness for the expandable formula bar in XL 2007...

jeffreyweir · Jul 17, 2013

OMG! I'll take a look. I may be some time...

SirJB7 · Jul 17, 2013

Hi, Luke M!

You deserve two Carlsbergs at least. What a pity that I've got only one left...

Regards!

PS: And it's mineeeeeee!!!

Luke M · Jul 17, 2013

Oops, forgot to clean up my formula. Number to be tested should be in cell J6, rather than the conventional A2.

Luke M · Jul 17, 2013

There, cleaned up a little, and shorted some ranges:

Code:

=IF(SUMPRODUCT((ROW(A:A)+((COLUMN(A:F)-1)*ROWS(A:A))<=INT(SQRT(A2)))*((A2-(ROW(A:A)+((COLUMN(A:F)-1)*ROWS(A:A)))*INT(A2/(ROW(A:A)+((COLUMN(A:F)-1)*ROWS(A:A)))))=0))=1,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(G:L)-1)*ROWS(A:A))<=INT(SQRT(A2)))*((A2-(ROW(A:A)+((COLUMN(G:L)-1)*ROWS(A:A)))*INT(A2/(ROW(A:A)+((COLUMN(G:L)-1)*ROWS(A:A)))))=0))=0,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(M:R)-1)*ROWS(A:A))<=INT(SQRT(A2)))*((A2-(ROW(A:A)+((COLUMN(M:R)-1)*ROWS(A:A)))*INT(A2/(ROW(A:A)+((COLUMN(M:R)-1)*ROWS(A:A)))))=0))=0,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(S:X)-1)*ROWS(A:A))<=INT(SQRT(A2)))*((A2-(ROW(A:A)+((COLUMN(S:X)-1)*ROWS(A:A)))*INT(A2/(ROW(A:A)+((COLUMN(S:X)-1)*ROWS(A:A)))))=0))=0,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(Y:AD)-1)*ROWS(A:A))<=INT(SQRT(A2)))*((A2-(ROW(A:A)+((COLUMN(Y:AD)-1)*ROWS(A:A)))*INT(A2/(ROW(A:A)+((COLUMN(Y:AD)-1)*ROWS(A:A)))))=0))=0,
IF(SUMPRODUCT((ROW(A:A)+((COLUMN(AE1)-1)*ROWS(A:A))<=INT(SQRT(A2)))*((A2-(ROW(A:A)+((COLUMN(AE1)-1)*ROWS(A:A)))*INT(A2/(ROW(A:A)+((COLUMN(AE1)-1)*ROWS(A:A)))))=0))=0,TRUE,FALSE))))))

Length: 1021

jeffreyweir · Jul 17, 2013

Crikey, Luke...in the time that formula takes to calculate, you can nip down to the shops, puchase two Calsbergs, drink one, then post back here that you just have one left and you're not going to share it with SirJB7 ;-)

But seriously, well done. You are the (current) silver medal winner, my friend.

SirJB7 · Jul 17, 2013

@TheGuyThatI'mNotReading

Hi!

Do you know I'm not reading you?

Regards!

@Luke M

Hi, my dearest friend!

I know you wouldn't be able to do such a blameworthy thing.

Regards!

Luke M · Jul 18, 2013

Thank you both for the kind words. And yes, it does take awhile. However, when you consider the sheet amount of numbers that single formula is processing...32.5 million numbers to check, it's more impressive. Would like to see the formula shorter, but had to break up the portions just so my machine wouldn't have a heart attack.

And only a silver medal? Who else has come up with a formula to find largest prime? <grin>

jeffreyweir · Jul 18, 2013

Only me! I'm hoping Sajan will join us, and wipe the floor with my one

SirJB7 · Jul 18, 2013

@Luke M

Hi!

That's not fair, you should have the gold medal for the time being...

There's a basic principle of law that says you can not be judge and jury at the same time, so the organizer should ethically abstain or participate without awards.

Regards!

Formula Challenge 006 - What's the largest number you can confirm is a prime?

Active Member

Excel Ninja

Active Member

Excel Ninja

Excel Ninja

Excel Ninja

Excel Ninja

Active Member

Excel Ninja

Active Member

Excel Ninja

Active Member

Excel Ninja

Active Member

Excel Ninja

Excel Ninja

Active Member

Excel Rōnin

Excel Ninja

Excel Ninja

Active Member

Excel Rōnin

Excel Ninja

Active Member

Excel Rōnin