Challenge Problem

[htirwin]

Here is a fairly simple programming challenge; an opportunity for some of the young talent to show their skills.

Respect will be awarded to the programmer who writes the most time efficient solution (multithreading welcome), the most interesting solution (recursion welcome), and the most elegant solution.

For the first 9 prime numbers (excluding 2),

3, 5, 7, 11, 13, 17, 19, 23, 29

3 + 7 = 10
5 + 11 = 16
7 + 13 = 20
11 + 17 = 28
13 + 19 = 32
17 + 23 = 40
19 + 29 = 48

10 + 20 = 30
16 + 28 = 44
20 + 32 = 52
28 + 40 = 68
32 + 48 = 80

44 - 30 = 14
52 - 44 = 8
68 - 52 = 16
80 - 68 = 12

The sequence: 14, 8, 16, 12 (for primes 3 through 29)

Your program should output the described sequence for primes from 3 to n.
After the sequence has been printed, print the maximum value in the sequence,
the minimum value in the sequence, the most commonly occurring value in the sequence (mode) (multiple if there is a tie), and the largest integer gap between consecutive terms in the sequence.

example output:

primes 3 to 29
(14, 8, 16, 12)
Max: 16
Min: 8
Mode: 14, 8, 16, 12
Largest Gap: 8 

[LB]

Which libraries are we allowed to use?

[htirwin]

You can use anything you want.

[LB]

Dang, I wish I was more familiar with boost.

[Script Coder]

What would the upper limit on n be?

[htirwin]

n should be set through user input.

Respect will also be awarded for wise/creative use of libraries (including the STL), and language features.

[Script Coder]

n should be set through user input

obviously, but algorithms might differ if n is <200 vs if n in <2000
must we just expect really high values of n?

[htirwin]

obviously, but algorithms might differ if n is <200 vs if n in <2000
must we just expect really high values of n?

How about 999,993.

[MiiNiPaa]

LB wrote:

Which libraries are we allowed to use?

iseeplusplus wrote:

You can use anything you want.

Shortest solution:

void doStuff();
int main()
{
    doStuff();
}

You should link MyCoolStuff.a though.

[LB]

All libraries have to be open source, then. I'm sure we can all agree :p

Still, thought, MiiNiPaa does raise a point - some libraries make this task blisteringly easy and elegant, even if their implementation is not.

[htirwin]

All libraries have to be open source, then. I'm sure we can all agree :p

Still, thought, MiiNiPaa does raise a point - some libraries make this task blisteringly easy and elegant, even if their implementation is not.

True, but you would only "win" best use of libraries "award" for that.

[MiiNiPaa]

I suggest to use only standard C++.
So no boost, no specific math libraries.

[htirwin]

I suggest to use only standard C++.
So no boost, no specific math libraries.

Ok.

[3qX21hU5]

Well I decided to give this problem a go in Python to see if I am actually learning anything from the last 2 days lol and because you didn't give a language restriction for this problem ;p.

Anyways here is my attempt, it seems to be working though I didn't do much testing on it since it is 5:30am and I just want to head to bed. It does run quite slowly if you get to numbers above 100k though but that is ok for now I will make it more efficient tomorrow.

from collections import Counter

def primes(n): 
    s = range(3,n+1,2)
    mroot = n ** 0.5
    half = (n+1) / 2-1
    i = 0
    m = 3
    while m <= mroot:
        if s[i]:
            j = (m*m-3) / 2
            s[j] = 0
            while j < half:
                s[j] = 0
                j += m
        i = i + 1
        m = 2 * i + 3
    return [x for x in s if x]
    
def first_stage(primeList):
    newList = []
    for each in range(len(primeList)):
        if each + 2 >= len(primeList):
            break
        number = primeList[each] + primeList[each+2]
        newList.append(number)
    return newList
    
def second_stage(myList):
    newList = []
    for each in range(len(myList)):
        if each + 2 >= len(myList):
            break
        newList.append(myList[each] + myList[each+2])
    return newList
    
def third_stage(myList):
    newList = []
    for each in range(len(myList)):
        if each + 1 >= len(myList):
            break
        newList.append(myList[each+1] - myList[each])
    return newList
    
def find_greatest_difference(myList):
    gaps = []
    for each in range(len(myList) - 1):
        if myList[each] < myList[each+1]:
            gaps.append(myList[each+1] - myList[each])
        else:
            gaps.append(myList[each] - myList[each+1])
    return max(gaps)
    
def find_mode(myList):
    count = Counter(myList)
    freq_list = count.values()
    max_count = max(freq_list)
    total = freq_list.count(max_count)
    return count.most_common(total)
    
limit = int(raw_input("Enter a max number:"))
myList = primes(limit)
myList = first_stage(myList)
myList = second_stage(myList)
myList = third_stage(myList)

print "Primes ", 3, " to ", limit
print myList
print "Max:", max(myList)
print "Min:", min(myList)
print "Mode (Number/Times Found):", find_mode(myList)
print "Largest Gap:", find_greatest_difference(myList)

[chrisname]

Technically, since Python is written in C using only the C standard library (AFAIK), of which the C++ standard library is a superset, a Python solution counts as a C++ one.

[MiiNiPaa]

C++ libraries are usually implemented using C/C++ standard libraries and C++ base language features, so almost any C++ library will counts as base C++ by your logic.

I think we should allow any language which uses only its owb standard libraries.

[3qX21hU5]

Fixed my solution to output the correct values for mode. Now working on the performance a bit (Though it runs pretty fast now for numbers up to a few million or so), and adding in some fun tricks to make it more elegant ;p Though I gotta look up some more features of Python first :(

Ohh ya nice little programming problem iseeplusplus was fun to work on.