Tough Problem 1

[pgc01]

Hi all

Many of us have fun creating solutions, imagining algorithms to solve difficult problems. Sometimes that's why we answer a question, because we think we'll have fun figuring out the solution.

I thought it would be a good idea if we posted, here in the lounge, complex problems to help us improve our knowledge in excel.

The idea is not to write a solution efficient, easy to read and to maintain. We do that in the excel forum. Here I thought we would try to push the formula/code capabilities to the limit. I'm talking about compact, ugly looking formulas, recursive algorithms, etc.

We will get solutions that we would not use in our work, but I believe it will help us to explore further the possibilities of the tools. Also the important is not the definitive solution, but the different ways to tackle the problems.

The problems should be complex enough to make even an experienced user feel some difficulty to solve them.


I will post the first one. It requires some background in mathematics.

Tough Problem 1

Background:

As we all know, the prime numbers have a very irregular distribution. Sometimes we find pairs of primes that are only 2 units apart, like (17,19) or (2549,2551). They are called Twin Primes. Their distribution is also very erratic, you find 2 pairs between 820 and 830 (821,823) and (827,829) but not even one pair between 900 and 1000!

Problem:

How many pairs of Twin Primes are there between 5 and N, with N<=10000?

Ex.:

For N=20 we have

(3,5),(5,7),(11,13),(17,19) - 4 pairs

For N=100 we add the pairs

(29,31),(41,43),(59,61),(71,73) - total of 8 pairs

The solution must work in excel versions before 2007 (to avoid formulas with 25 nested parentheses).


Criteria for ranking of the solutions:

1 - less formulas is better
2 - cleverer, simpler solution is better

To the mvp's and experienced users: If you find this simple or already know a solution, please don't post it in the next hours to allow everyone to have some fun trying to figure it out.


Here is a link where you have the first 35 twin primes pairs:

http://en.wikipedia.org/wiki/Twin_prime

Don't forget, the idea is to have fun!!!

-----
P. S.
Do you think this makes sense?

Remark:
It may also happen that none of this makes sense and it's all the product of a disturbed mind.

 

[barry houdini]

How many pairs of Twin Primes are there between 5 and N, with N<=10000?

Hello pgc,

I don't have an answer (yet ) but I like the concept........

You say between 5 and N but list (3,5) as a pair, do you mean between 2 and N?

regards, barry

 

[pgc01]

Hello pgc,

I don't have an answer (yet ) but I like the concept........

You say between 5 and N but list (3,5) as a pair, do you mean between 2 and N?

regards, barry

Hi barry

No, I did mean between 5 and N, I should not have included the pair (3,5) in the examples.

Not many action here. I still think the concept is good. Maybe this was a bad choice for a first problem?

cheers

 

[Domski]

Do you think this makes sense?

It makes sense to me however I fear my frankly woeful maths skills will be below what is required.

I do like the concept though and will have a stab at it and look forward to seeing some of the solutions provided.

It's somewhat coincidental that you posted this as I came across Project Euler (http://projecteuler.net/) the other day and it got me thinking about similar challenges that I might be able to have a go at.

Best of luck folks,

Dom

PS If there's anyone in the class who I can copy off you can have half my dinner money

 

[Jonmo1]

Are you looking for only formulas, or will VBA functions be accepted?

=TwinPairs(5,100)

Public Function TwinPrimes(lownum As Double, highnum As Double)
Dim x As Long, i As Long
Dim MyPairs As String
x = 0
For i = lownum To highnum
    If isprime(i) Then
        If isprime(i + 2) Then
            x = x + 1
            MyPairs = MyPairs & " (" & i & "," & i + 2 & ")"
        End If
    End If
Next i
TwinPrimes = "There are " & x & " Twin Primes Between " & lownum & " And " & highnum & MyPairs
End Function
 
 
Public Function isprime(myval As Variant) As Boolean
Dim devisor As Double
Dim x As Double
isprime = True
For devisor = 2 To myval - 1
    x = myval / devisor
    If x = Int(x) Then 
        isprime = False
        Exit For
    End If
Next devisor
End Function

Also, I'm not sure about this.
Is there a built in IsPrime function, or did I reinvent the wheel?


Love the concept of the thread as well.

 

[Jonmo1]

I noticed an error in the logic. It will give eroneous result if the Highest or Highest-1 Number is a prime.

Just change
For i = lownum To highnum
to
For i = lownum To highnum - 2

it will also be eroneous if lownum is 0-3, but the challenge stated to begin with 5, so to comply with that requirement, add a single line at the beginning

If lownum < 5 then lownum = 5

 

[pgc01]

Domski, thank you for the link, it's very interesting. I'll be spending some time there. As for the difficulty because of the required mathematical background, I agree. This may be the reason why there haven't been more posts so far (I hope).


Jonmo, thank you for posting, I'm expecting a formula solution. One of the sub-problems is to generate the list with the primes.


I'm posting a second problem for the vba fans. I think it's interesting to have both problems running at the same time, we know that many of us prefer formulas and other vba, so everyone is happy. Also it's very easy to understand and that may please more people.

 

[cornflakegirl]

Jonmo - I love how simple that solution is!

I think you can replace
For devisor = 2 To myval - 1
with
For devisor = 2 To Int(Sqr(myval))

possibly slightly faster?

(PGC - apologies for hijacking with further VBA...)

 

[pgc01]

PGC - apologies for hijacking with further VBA.

Hi Emma

On the contrary, thanks for posting. The better you understand the algorithms the easier you'll build the formulas.

possibly slightly faster?

No, much, much faster. You should always use it when testing primes, and the bigger the number the more important that modification is.
Another thing you can do is to get rid of the even numbers.

This is another code to test the number

Function IsPrime1(lVal As Long) As Boolean
Dim l as Long
 
If (lVal = 1) Or (lVal > 2 And lVal Mod 2 = 0) Then Exit Function
 
For l = 3 To Int(Sqr(lVal)) Step 2
    If lVal Mod l = 0 Then Exit Function
Next l
IsPrime1 = True
End Function

If you test them, for example with a loop that tests the numbers from 2 to 50000 you see how faster it is.

P. S. Have you checked my other problem? Since you have a strong mathematical background you may find it intersting.

 

[Jonmo1]

For devisor = 2 To Int(Sqr(myval))
possibly slightly faster?

I don't understand why that would make it faster...
All that does is reduce the number of loops.

this bit does the same thing

    If x = Int(x) Then 
        isprime = False
        Exit For
    End If

declares isprime false and exits the loop once the first evenly divisible number is found.