Largest prime number

[parksie]

We now have a new largest prime number!

http://www.utm.edu/research/primes/notes/3021377/

[[Digital-X-Treme]]

The whole Primes project reeks of geek... but i love it How about we do something similar here on VB-World, kind of as a project... Obviously not on the same scale as the prime project, but we could have competitions to do with math stuff, like finding the biggest, smallest etc etc... Any ideas?

Later

[Sam Finch]

I have to agree with D-Xtreme about the geekiness of the primes project (there's loads of money in it tho') I have to admit having a bash at finding a formula for them though, I got quite close as well, I found a way of finding sets of about 6 nonlinear equations, and If I found one with whole number solutions then they could be used to get a function which would always produce primes. Unsurprisingley I never found the right set of equations. (I doubt one actually exists) I can't remember the maths involved, otherwise we could have had a bash at that. (we'd fail, but who cares)

Can't think of any other challenges at the moment, but I'll post if I think of any.

[parksie]

Love the sig, Sam

And I think that the primes thing is a bit geeky, but no more so than finding Pi to the nth decimal place...which I admit to attempting to write software for. Unfortunately I had difficulty writing a string ArcTangent function

[Sam Finch]

Well finding primes is actually useful, and involves some very interesting (and horrendously difficult) maths. whereas finding pi to the nth decimal place is essentially pointless. I've just had a quick look at it and the only vaguley interesting thing I can find about it is this problem.


Find an algorithm that given any whole number N we can find the smallest number s sutch that

(10^s) - 1 is divisible by N

if you can find an efficient algorithm to do that then it's pretty simple to put something together that can find Pi to lots of D.P. pretty quickly. and to be honest I've got better things to do. (sit here and scratch my arse for example.)

[Lord Orwell]

i postem some code not too long ago in the General area that found all prime numbers in a range you specified, and put them in a list box.
It worked like this: Since all smallest factors of a number are prime numbers, i simply divided a number by each prime number under it and checked for a remainder. It was extremely fast. Say you enter a range of numbers from 1 to 100000. In 15 sec (on my comp) you would get your range. It automatically put the value 2 in the text box. Then when it came to 3, it tried to divide it by the only prime smaller than it: 2. it got a remainder so it entered 3 in the text box. (for speed i didnt actually use the text box until all # were found- until then all # were kept in an array).
when it came to 4, it divided by 2 and found no remainder so it didnt enter it. 5 it divided by 2 and 3 and found remainders so entered it. etc.
Also, it only tried the primes that were smaller or equal to 1/2 of the number. If you do a search, im sure you will find it.

[Guv]

The quest for a formula or algorithm which produces primes has a long history. There was a time when it was a holy grail quest for mathematicians.

I think the original quest was for Function(N) which would produce every prime in order. Id est: F(1) = 2, F(2) = 3, F(3) = 5, F(4)= 7, F(5) = 11 . . . . et cetera. I think they gave up quick on this quest.

Then they decided to try for an algorithm which produced an unbounded number of primes, but which might omit some. Various formulae were proposed for this. At least one such formula was believed to be valid because some of the huge numbers it produced could not be factored for a long time after the formula was proposed.

Nobody has ever succeeded. I do not know if anybody ever proved that it was impossible to find such an algorithm. My guess is that it is impossible.

[HaxSoft]

If you guys were to set up a project as [Digital-X-Treme] suggests, then I have a "thing" for you to crack:

If I XOR a message with a 3-byte key and then later Xor the result with a 17-byte long key then I know the 3-byte gets repeated and so does the 17-byte long key.

HOW can I calculate when these repetitions "meet"?

To clarify the question: The 3-byte key will repeat and might -- in fact be applied repeatedly to the 17-byte long key to form a "combined" key that would decrypt the message. How long is that "combined key"? -- for any two key lengths?

What the #¤%&/( is the formula?

Man, I don't think you will understand this question, but I sure hope so.

[Lord Orwell]

Simple. If one of the numbers is not a factor of the other number, then you multiply them together.

or in programming (vb)
if a mod b = 0 then
if a >= b then c = a else c = b
else
c = a * b
end if
msgbox "pattern repeats every " & c & "bytes"

[Sam Finch]

Lord O,

close but no cigar.

The number you are looking for is called the lowest common denominator of the 2 numbers (or lowest common multiple if you're american) It's the lowest number that id divisible by both of the numbers.


The way to find it involves finding the highest common factor of the 2 numbers.

The Highest common factor is the highest number that divides both of the numbers (for example the highest common factor of 4 and 6 is 2, because 4 = 2*2 and 6 = 3*2) the best way to find the highest common factor of 2 numbers is by brute force.

Public Function HCF(a As Long, b As Long) As Long

    Dim i As Integer 'a counting Number

    i = IIf(a > b, b, a) 'set i to the lower of the 2 values

    Do

        ' the if block succeeds if i divides a and i divides b
        If (a Mod i = 0) And (b Mod i = 0) Then

            'i is the highest common factor
            HCF = i
            Exit Function

        End If

        i = i - 1  ' keep decrementing i until we find a common factor

        'there's no need to stop the loop as 1 is a common factor of any 2 numbers
        'so it will stop itself if it gets down to 1
     Loop

End Function

If the 2 numbers are very big (in the millions) then it's worth doing it a different way, but it's much more complicated so I won't bother

to find the lowest common denominator multiply the 2 numbers together and divide by the highest common factor

Public Function LCD(a As Long, b As Long) As Long

    LCD = a * b / HCF(a, b)

End Function

and that'll give you your repeat rate.

[Lord Orwell]

oops

I forgot to take that into account.
dim x as integer
dim y as integer
'assign x the size of one string
'assign y the size of the other
dim pattern as integer
dim smallernum as integer
dim largernum as integer
if x < y then
smallernum = x
largernum = y
else
smallernum = y
largernum = x
do
pattern = pattern + smallernum
loop until pattern mod largernum = 0
msgbox "common factor length = " & pattern

[paulw]

I have to take issue with the initial assertion of Parksie that we 'have a new prime number' - we've always had it we just hadn't discovered it and it is not the highest prime in existence just the highest currently known published prime. There may be somebody out there who knows a dozen more...

Call me picky, but I'm right hehehehehehehe...

Cheers,

P.

[Guv]

PaulW: When dealing with mathematics, you should be picky. However, there are those (not me) who would argue with you on this issue.

There is a dippy philosophical argument about a statue of a horse. A sculptor takes a block of marble and makes a beautiful statue of a horse. Did the sculptor create the statue? Was the horse always there in the block of marble? I do not think there is much argument about the statue: I believe that the sculptor created it. There is a similar argument about discoveries in mathematics, which seems more controversial to me (and others). Some claim that mathematical discoveries do not exist until some body invents or discovers them. This point of view is similar to the claim that the horse did not exist until the sculptor created it.

Lord Orwell: You can speed up your search for primes a bit by skipping even numbers. If you want to get a bit trickier, you can start with a multiple of seven and add 6. Check the number and the number that is two below it. For example, check the following: 13, 11, 19, 17, 25, 23, 31, 29, . . . 121, 119, 127, 125, . . . .

I do not understand why you stop when you get to half the upper bound. If searching for primes between 1 and 100, note that 97 is a prime, and there are others between 50 and 97.

[Lord Orwell]

You evidently don't understand how the program works. I don't stop the search at 1/2 the upper bound. I stop dividing when i reach a number that is greater than 1/2 the value of the number i am checking.
Also, If you examine my code, you will see that i am in fact eliminating numbers by determining if they have prime numbers as a factor. 7, 13, etc.
Every prime I find is divided into the search for prime numbers greater than twice its size.
I suppose i could have slightly increased the speed if i had incremented in steps of 2 instead of 1. But since the first comparison was to check if 2 factored into it, it gets eliminated pretty fast.

[kedaman]

I recall i made my prime number enumerator roughly 6 years ago, in vb 1. I quickly discovered i didn't need to loop trough more than half of each number i was checking, but later on also, all numbers beyond the squareroot of the number i was checking. For instance, if I was checking the number 42, i wouldn't need to divide by more than int(sqr(42)) which is 6, since they all appear in pairs (like 6*7 and 2*21), of which no pair can be larger than sqr(42). I didn't know about how slow squareroots was back then, but even if i did, the process would still be tons faster for huge primes. I didn't have a fast comp back then, a 66mhz 486 if i remember correctly, but stilll i could check huge numbers like 1E12, since that would only need 5E5 cycles, which a half million times faster than 2.5E11.
I did not use modulus or integer division though, even if didn't know they were faster, but floating point division, which on the other hand could handle values larger than 2^31, which is 2E9. A lot later, i think about a year ago, i made a lookuptable which stored all prime numbers found in an array, and only divided the numbers to check for with primes, although this way you can't start searching from whatever number you desire.

[simonm]

Guv,

Why do you call that particular philisophical view point dippy? It's not that things don't exist until we 'create' them, indeed they exist, it is just the 'meaning' that we create.

Someone once said:

The laws of nature are not eternal, abstract truths. They are patterns that prevail in some chosen context: The laws that you find depend upon the questions that you ask.

[paulw]

I once heard a talk by a sculptor who talked about freeing the sculpture hidden by the extra material around it.

You could, I suppose, argue that Mathematics is a formal language which contains abstractions of human concepts representing some form of truth. If numbers exist independently of humankind then all Prime numbers already exist. Alternatively, we could claim that the numbers don't exist until we invent them since they are conceptual only...

You can have the same argument about moral relativism. You know, Guv, youand I always stray into philosophy when talking about maths. I've missed our conversations. We could start a philosophy thread...

Cheers,

P.

[simonm]

I believe that when one talks about Mathematics on a conceptual level, it is inseperable from philosophy.

In fact, if you look back over time at many of the great philosophers, you will notice that many of them were also mathematicians as well.

I believe that not enough emphasis is put on the conceptual side of maths in schools (too much on the mechanics) and that is why maths is generally an unpopular subject. We learn the mechanics of mathematical operations without any regard as to why it came about or how it fits in with other ideas.

[paulw]

Quite right - not bad for a yokel...

BTW I am from the Isle of Wight, so I am a country boy dazzled by the bright lights...

Cheers,

P.

[simonm]

Well I'm from london (originally) and I'm now wandering like a lost lamb in the darkness of the countryside!

[HarryW]

I went to the Isle of Wight once.... I don't plan on going back if I can help it.

[Lord Orwell]

Hmm there are things in quantum mechanics that aren't fixed until they are observed. who is to say that other things aren't the same? Perhaps a mathematical law doesn't exist until someone tries it

[paulw]

Actually they are fixed until observed - the act of observation moves them... Heisenberg's Uncertainty Principle - you can be sure of position or velocity, but not both...

Harry - I used to like you... Mind you, you probably went to the East Wight. Went to Guildford once and I don't plan on going back there either....

Cheers,

P.

[simonm]

paulw,

That's not quite right I'm afraid. An un-observered quantum system exists as a superposition of all possible states that are defined by it's wave function.

The act of observation collapses the wave function and yields a definite state.

Heisenberg's Uncertainty Principle dictates that you cannot know two 'complementary' properties of a quantum particle simultaneously. You cannot be sure of either property until you make a measurement, and then, the more precisely you measure one property, the more uncertain you become about the other property.

[Fried Egg]

Perhaps the largest prime number we know about is the largest prime number. As time passes, we might assign the status of 'prime' to higher and higher numbers but all we are doing is attaching a contextual meaning to an otherwise arbitary number.

Any numbers larger than the largest prime number, although they may be determinied at some future date that they are in fact prime, for the time being may not be treated as such. For the meaing that being 'prime' attaches to a number, is what allows it to be treated as such.

We must not forget that numbers are just mental constructs that we use to build imaginary models that help us simplify and understand the world.

Does everything we could possibly imagine or construct with our minds already exist and is just sitting there waiting to be discovered?

[paulw]

Simon,

If you want to get technical on this one, the wave function is only a representation of the state of a particle, the actual wave/particulate nature of matter is not precisely definable... Hmmm, sounds like a philosophical concept coming up again.

For now, I appreciate that though you live in Devon you are not entirely unsophisticated....

Have a good weekend...

Cheers,

P.

[Lord Orwell]

I like it when someone else proves me right
Usually I have to do it myself