Finding Prime numbers using Euler's formula

[ex81]

Homework Statement

use Eular's formula to find the greatest prime number under :
If I wasn't forced to use this method I would set up a program to loop through checking for primes

Homework Equations

F(n) = n^2 + n + 41(0 to 39)

or depending on your PoV

f(n) = n^2 - n + 41(1 to 40)
Where the number is above 41

The Attempt at a Solution

Now I'm not even sure where to start with this mess as I do not understand how the "formula" is supposed to work

But my first number is 68, so f(68) = 68^2 + 68 + 41.
= (40 + 28) ^ 2 + (40 + 28) + 41

Now I do not see any rational of what to do next.

 

[mfb]

It is Euler, not Eular.

Homework Statement

use Eular's formula to find the greatest prime number under :

Under what?

Homework Equations

F(n) = n^2 + n + 41(0 to 39)

or depending on your PoV

f(n) = n^2 - n + 41(1 to 40)
Where the number is above 41

Those formulas just generate a small set of primes - not all, and with many gaps in between. And for n outside the range, the number is not always a prime number. In general, the smallest prime below some number will not be covered by that formula.

Now I'm not even sure where to start with this mess as I do not understand how the "formula" is supposed to work

Start with the full problem statement?

But my first number is 68, so f(68) = 68^2 + 68 + 41.
= (40 + 28) ^ 2 + (40 + 28) + 41

Now I do not see any rational of what to do next.

Are you sure you are supposed to use 68 in that formula?

 

[ex81]

1)my assignment as posted:

"Hash Table

Want it your way? Now's your chance! Instead of me assigning predefined header files, prototypes and whatnot, I'm going to give you the opportunity to design and implement a solution to a problem entirely on your own. All you have to do is design and implement an ADT to function as a hash table! To keep things simple, all your program has to do is read integer values from stdin and insert them into the table. Although each implementation will certainly differ significantly, there are some constraints that we'll agree on:

Your implementation has to be entirely your own code from scratch, no external libraries with pre-built components (e.g., the Standard Template Library).

You'll provide a complete implementation of the program, which means not only the ADT but also the test driver.

You should use the object-oriented techniques in C++ to create a class ADT for your hash table. Follow the book's approach in designing the ADT – first think about what operations are going to be necessary, sketch out an operations contract, which eventually will lead you to filling in a functional specification.

We'll be using “open addressing” (p.550), and the size of the hash table will be contained in a header file I'll give you called hashdefs.h, so you'll need to #include this file in your source code anywhere the size of the hash table is required.You'll find a copy of this file in the Project2 directory of your ssh account.

The hash function will be a simple “modulus” operation, where the hashed index is the remainder of dividing the search key by the size (capacity) of the hash table.

As we saw in class, there are several methods to handle collision resolution, but the one you'll implement is double-hashing (p.552); you can use h2(x) = R - (x % R) with "R" being the largest prime number smaller than the size of the hash table. A simple way to derive this prime number is to use Euler's equation of n2+ n + 41, which will produce prime numbers for n < 40. This means that the size of your hash table has to be greater than 41 and less than 1,608, but that's a constraint we can live with! The resulting number can then be used in your second hash function should you need to resort to double-hashing.

The final executable should be able to read integer values from stdin so I'll be able to test it by using redirection on the command line. The number read from stdin should be submitted to a hash table member function that will take it from there and attempt to store the integer in the ADT. So do whatever you want in your code to help you during the development phase, but the final executable should be able to run like this:

./a.out < ints.txt > results.txt

Your program should indicate what is happening as integers are inserted into the table. Since you'll be writing all your messages to stdout, I'll be able to collect whatever you're writing out into an output file (again, using redirection) and examine its contents after a program run. What kind of messages should you be writing to stdout? The way I see it, there are basically three types of messages that would be interesting to see: if a number is successfully inserted into the table, if a number cannot be inserted into the table (because there isn't an available location), and if a number can't be inserted because it's already in the table. We should agree on the format of each of these messages so that the output is consistent among different implementations, so here's what I suggest:

success: 42551 // 42551 was successfully inserted into the table
failure: 42551 // 42551 cannot be inserted, no available location
exists: 42551 // 42551 already exists in the table
"

Which is largely irrelevant to my issue. Now to your question of what number it can be anything, which is why I posted the question as "use Euler's formula to find the greatest prime number under :" As per the assignment the starting number can, and likely will change based upon some unknown criteria.



2) I fully understand that the "formula" that I am required to use will miss some prime numbers. I've been beating myself against this thing for 3 days now, and I have no concept of how it does anything except cause me no end of frustration.




3) 68 is the starting point I was given, and I need to check the numbers below it until I find the "largest" prime number. The point is that all of us use the same "formula" for finding prime numbers.

 

[scurty]

The formula is a function. Input any number $n$ from 0 to 39 (for the first function you listed) and $f(n)$ will output a prime.

So, the brute force approach for finding the largest prime (using the formula) under 68 would be to start with $n = 0$ and increment $n$ until $f(n) > 68$. The previous value for $f(n)$ would be your answer.

e.g. $f(4) = 61 \, f(5) = 71$. 61 would be your "largest" prime under 68 using the formula.

I'm sure there is a more efficient way for programming the code if you wanted, but $f(39)$ isn't exactly a huge number.

I think I addressed your confusion?

 

[ex81]

Some of it but how is is f(n) = n^2 + n + 41 supposed to tell me that it is a prime number?

 

[scurty]

That formula generates primes for n between 0 and 39 inclusive. A simple check of the 40 numbers generated will tell you so. However, when n hits 40,

$f(40) = 40^2 + 40 + 41 = 40(40+1) + 41 = 41 (40+1)$

and the result is no longer prime. In the context of the question, you are told that the function outputs prime numbers for those values of n.

A simple way to derive this prime number is to use Euler's equation of n2+ n + 41, which will produce prime numbers for n < 40.

 

[lurflurf]

You problem is not clear. As I understand it your formula gives 40 primes, so your task given a number is to find the largest prime less than the given number. There are many ways to do this. Two obvious ones include
1)List all the numbers
find the number
for 68
we have
61<68<71
so 61
2)solve y=x^2+x=41
by the quadratic formula or otherwise
68=x^2+x=41
x = 4.7202
x=4;y=61

of course the program should return an error for y=41 and lower
and 1601 for all y>1601

 

[ex81]

@Scurty That means absolutely nothing to me. I don't have any clue how f(n) = n^s + n + 41 gives me anything useful.

@lurflurf The problem is I have no clue how, or what f(n) = n^2 + n + 41 is supposed to do anything. That is my issue. Based on your answer i am to monkey with the quadratic equation somehow.

based on your answer, and what I posted initially, i would have this:
f(68) = (68)^2 + 68 + 41

therefore

f(68) = 4733

which again makes no sense.

Looking at it from a standpoint of f(68) = (1)n^2 + (1)n -27; (41-68 = -27). Where a & b equal 1, and c = -27
I get a number that is basically zero. Which is useless.

 

[Office_Shredder]

@lurflurf The problem is I have no clue how, or what f(n) = n^2 + n + 41 is supposed to do anything. That is my issue. Based on your answer i am to monkey with the quadratic equation somehow.

The point is that for your hash table you are going to say 'gee, I wish I had some way of generating prime numbers'. The teacher is giving a formula which is known to, by sheer coincidence basically, give prime numbers if you plug in any integer between 1 and 40. It just happens to work and is a convenient way of generating nontrivial prime numbers without having to do any actual work. That's all it is.

 

[ex81]

Thank you Office_Shredder for restating what I already knew, AND answering my issue:

("give prime numbers if you plug in any integer between 1 and 40.).

" I full well know what a prime number is, and how I would generate them BUT my professor said here you go, and you have to use it without explaining that equation. Having NEVER seen, nor heard of Euler before last week, I had zero basis to make a deduction. And as you can see above I was thinking in different terms.

 

[lurflurf]

You would not find
f(68) = (68)^2 + 68 + 41
you would find that
f(4.7202)=4.7202^2+4.7202+41=68
then
f(4)=4^2 + 4 + 41=61

The simple version is we have the 40 numbers
F(0),F(1),...,F(38),F(39)
Given some other number such as 68 we are to determine which number less that 68 is largest
Since in that case F(0)=41,F(1)=43,F(2)=47,F(3)=53,F(4)=61 are less than 68 and the largest of them is
F(4)=61