• 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 006 - What's the largest number you can confirm is a prime?

jeffreyweir

Active Member
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

Excel Ninja
Staff member
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/
 

Luke M

Excel Ninja
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

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

=SQRT(A1)

and check the results.
 

Luke M

Excel Ninja
@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

Excel Ninja
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

Active Member
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

Excel Ninja
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

Active Member
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

Excel Ninja
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

Active Member
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

Excel Ninja
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))<=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))<=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))<=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))<=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))<=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))<=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))<=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]
 

Luke M

Excel Ninja
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

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

SirJB7

Excel Rōnin
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

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

Luke M

Excel Ninja
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

Active Member
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

Excel Rōnin
@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

Excel Ninja
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? &#60;grin&#62;
 

SirJB7

Excel Rōnin
@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!
 
Top