Excel Challenge #8

Got Excel skills? Let's see.

Hoping that this one is a little more doable

Here are the usual rules.

• Create a single Excel formula to solve the stated problem.
• The shortest formula wins (when calculating the length of the formula there's no need to include the leading "=", or the curly braces that Excel uses to represent array formulae).
• The formula's number format can be set to whatever you want.
• Conditional formatting is not allowed.

Problem #8

Assume that cell A1 contains a positive integer value. Create a single formula to determine whether or not the value in A1 is prime. The output should be either TRUE or FALSE. For example

A1
2 --> TRUE
16 --> FALSE
17 --> TRUE
120 --> FALSE
1024 --> FALSE
472882049 --> TRUE
982451652 --> FALSE
982451653 --> TRUE
982451654 --> FALSE

 

That's great, but what about the big numbers?

 

I think that should be "^2" rather than "^0.5" (and I'm not sure about the "+1" either ). Either way we could check for values A1 < 1,099,511,627,776. Now this is about 10^12, and Excel only displays number with up to 15 digits of precision - after that it will use trailing zeroes in which case it won't think there are more primes . It might possible to use the Sieve of Eratosthenes to boost the search from 10^12 to 10^15.

This leads to an interesting question; what is the largest prime number Excel can display?

 

You're current submission looks like

Code:

=SUM(1*(MOD(A1,ROW(OFFSET(A1,,,SUM(A1))))=0))=2

By changing the SUM to SQRT would give a substantial increase (assuming that the "=2" goes to "=1" as well). This leave

Code:

=SUM(1*(MOD(A1,ROW(OFFSET(A1,,,SQRT(A1))))=0))=1

This checks every number between 1 and SQRT(A1) for a potential factor, but we know that once "2" has been checked then all other even numbers can be ignored. Something like this might work;

Code:

=SUM(1*(MOD(A1,1+2*ROW(OFFSET(A1,,,SQRT(A1)/2)))=0))=1

This checks odd numbers between 3 and SQRT(A1), but the OFFSET function can now handle twice as many rows. Would this double the searching power? If so, then a similar process might be implemented for multiples of 3, 5, 7 and 11. I think that this would boost the search sufficiently well to reach 15 digits.

 

Here are a couple of implementations of the Sieve of Eratosthenes:

Based on primes 2 and 3

Code:

=PRODUCT(--({2,3}*INT(A1/({2,3}))<>A1))*PRODUCT(--(MOD((A1/({1,5}+2*3*ROW(OFFSET(A$1,,,SQRT(A1)/2/3)))),1)<>0))=1

Based on primes 2, 3 and 5

Code:

=PRODUCT(--({2,3,5}*INT(A1/({2,3,5}))<>A1))*PRODUCT(--(MOD((A1/({1,7,11,13,17,19,23,29}+2*3*5*ROW(OFFSET(A$1,,,SQRT(A1)/2/3/5)))),1)<>0))=1

By extending this to include primes 2, 3, 5, 7 and 11 then Excel can verify that 999,999,999,999,989 is prime, and therefore the largest that it can represent. The formula is pretty long (1,650 characters) because it needs to include the list of primes less that 2*3*5*7*11=2,310.

Watch out for the 2-dimensional array formula here - I don't think it's been used in the Challenges before and could be useful in the future

 

Watch out for Excel Challenge #9 - launching Friday 9th October 2015.