Please visit donation page to help the project cover running costs for this month
1) Message boards : General discussion : Badge colours (Message 160358)
Posted 232 days ago by Ravi Fernando
Nice concept, but there's problems.

Show me the Gold (500K), Double Silver (200M), and Double Gold (500M) badges, and you'll get my attention.

You'll notice none of the badges have more than 3 letters in one row. Four don't fit, at least if you want them to be readable.

To be honest, I'm more curious how one could add more text to the sieve badges. They look pretty full to me.

An alternative idea (which probably everyone will have their own opinion on) would be to display badges in order from highest credit to lowest. That way you could get a rough idea of how impressive someone's badges are just from mousing over the first few. As it is, it's possible to overlook one or two particularly high-credit badges--e.g. if you don't notice Peter's GFN emerald and AP jade, you might think he only has about as much credit as I do, when in fact he has 9x more.
2) Message boards : General discussion : Findings In Challenges (Message 159543)
Posted 249 days ago by Ravi Fernando
Surely robish's AP27 (found during an AP27 challenge) counts as notable!
3) Message boards : Number crunching : Badges III (Message 159279)
Posted 260 days ago by Ravi Fernando
4) Message boards : Number crunching : Badges III (Message 158979)
Posted 273 days ago by Ravi Fernando
Missed this one a while back:
5) Message boards : Problems and Help : Проблема Серпинского (Message 156762)
Posted 404 days ago by Ravi Fernando
Copying from Google Translate for those of us who don't speak Russian:
Now, in order to speed up the verification process, we will configure and remove unnecessary
numbers take the candidate
and get numbers to check only in these sequences
may be prime numbers.


I think "80" is a typo: 1+21181*2^(80+120n) is always divisible by 17. On the other hand, 1+21181*2^(20+120n) does not generally have any small factors. But other than that, yes, these are the only exponents that can produce Proth primes with k=21181, because all other candidates are divisible by a prime p <= 17.

This is an example of sieving: removing candidates that are divisible by small prime numbers. For the Seventeen or Bust project, the sieving was done in the (now suspended) PSP Sieve subproject, which appears to have gone up to p ~ 104P = 104 * 10^15. So all candidates that are divisible by a prime of this size or smaller have already been removed from the search, and we are only testing the remaining (possibly prime) candidates in SoB.
But we can say with confidence that a prime number is in them in each separately.

Very likely true--but surely Seventeen or Bust is hard enough already!
I would choose to test one of them.
If you are interested and have not looked for it, I can set up any candidate, smaller and larger.

I would encourage you to run the Seventeen or Bust subproject if you're interested in this. A lot of smart people (and a lot of fast computers) have worked hard to make the search run as efficiently as possible. There's no need to reinvent the wheel.
6) Message boards : Number crunching : Main Tasks and Proof Tasks (Message 156319)
Posted 442 days ago by Ravi Fernando
I have just returned a PSP task that appears to have been a "Main" task (over a day to run) and it is showing now as a "Proof Task", what is that?

Yes, the PSP task you returned was a main task (i.e. your computer was testing some large number for primality). The "[Proof task]" text that you see in its status field is a link to the corresponding proof task (i.e. a short task that someone will run to quickly confirm your computer's calculations); that proof task hasn't been sent out yet. Similarly, your computer completed a PPS proof task a few days ago, and you can see a link to the corresponding main task.
7) Message boards : Sophie Germain Prime Search : Sophie Germain Prime Search (Message 155250)
Posted 518 days ago by Ravi Fernando
Why did the search jump from n=666666 to n=1290000? Is there something special about these exponents? Are they more likely to produce SG primers than others?

There's nothing mathematically special about them. We search with a fixed n and varying k in order to generate lots of candidates without the numbers getting significantly bigger. When we finished the range that was sieved with n=666666, we moved on to a larger n for a bigger challenge. Lennart was in charge of things in those days, and he coordinated some testing to decide the exact value of the next n. It turned out that computations got significantly slower between n=1290000 and n=1310000 (presumably because of an increase in FFT size), so 1290000 was the natural choice.
8) Message boards : Number crunching : hey! a more efficient sieve for b*2^k+1 (Message 155249)
Posted 518 days ago by Ravi Fernando
It is because the smaller factors have (order of 2) < k so they cover k with k = n * (order of 2) + offset with n > 0,
while the larger factors have (order of 2) > k, and the only way to equal k when n is 0 is to have their offset == k.

I think composite factors would follow this behaviour as well.
$ echo 25 | ./cycle_filter 21181 pri=25 len=24 off=2 $ echo "21673 5 * p" | dc | ./cycle_filter 21181 pri=108365 len=10836 off=122

NB the program just prints "pri=", it doesn't expect the divisors to be prime.

Looks correct to me, except that the order of 2 mod 25 is 20, not 24. Maybe a slight bug in the case of divisors with repeated prime factors?
9) Message boards : Number crunching : hey! a more efficient sieve for b*2^k+1 (Message 155243)
Posted 519 days ago by Ravi Fernando
Then I ran the unique factors of S122 through program_A
obtaining the unexpected result that all the factors > 163 of S122
have the same starting offset as 163.

That seems very expected to me. The offset of p is by definition the smallest k such that p divides 21181 * 2^k + 1. So you found a bunch of prime factors of 21181 * 2^122 + 1, calculated their offsets, and discovered that... all of them divide 21181 * 2^122 + 1, and most of them (the big ones, at least) don't divide any smaller number of the form 21181 * 2^k + 1. What's surprising about that?
10) Message boards : Number crunching : hey! a more efficient sieve for b*2^k+1 (Message 155226)
Posted 520 days ago by Ravi Fernando
What I notice is that when the order of 2 in the multiplicative group formed by 2^k+1 (mod p) is p-1,
then 2 is a generator with the same order in the multiplicative group formed by b*2^k+1 (mod p),
and the cycle of residues b*2^k+1 (mod p) for k = 0 .. p-1 is simply a rotation by "e" positions
of the same cycle of residues of 2^k+1 (mod p). I haven't proven this, it's just a pattern I see.

How I would phrase this: the subgroup H generated by 2 in (Z/pZ)* has the same size as its coset bH. (That is, powers of 2 mod p cycle with the same period as b times powers of 2.) Moreover, if 2 is a generator of (Z/pZ)* (a primitive root), then the list b*2^k is the same as the list 2^k shifted cyclically by e steps, where e (a discrete logarithm) is chosen so that 2^e = 1/b mod p. This is all true, provided of course that b is not itself a multiple of p.
The ideal situation would be to have a formula which relates b, p, and e.

It sounds like you're looking for an efficient solution to the discrete log problem. If you find one, I'm sure the NSA would love to have a word with you.

Next 10 posts
[Return to PrimeGrid main page]
Copyright © 2005 - 2023 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 1.37, 1.33, 1.62
Generated 29 Sep 2023 | 13:52:32 UTC