Search the web
Sign In
New User? Sign Up
primenumbers · Prime numbers and primality testing
? Already a member? Sign in to Yahoo!

Yahoo! Groups Tips

Did you know...
Message search is now enhanced, find messages faster. Take it for a spin.

Best of Y! Groups

   Check them out and nominate your group.
Having problems with message search? Fill out this form to ensure your group is one of the first to be migrated to the new message search system.

Messages

  Messages Help
Advanced
Programming Question   Message List  
Reply | Forward Message #4801 of 21107 |
Re: Programming Question

--- In primenumbers@y..., Phil Carmody <fatphil@a...> wrote:
> In other words, given non-square n, what's the size of the smallest
b that is a square-denier (yes, neologism) for n.
>
> Is there a case where the smallest square-denier for n is >sqrt(n)
(done without taking a square root, of course!)
> In Marcel's case the smallest square denier is b=2^2, for reference.
>

Cases of non-square n with smallest square-denier > sqrt(n):

n square-denier(n)
---------------------
2 3
3 4
5 3
6 4
7 4
8 3
10 4
12 5
13 5
15 4
21 8
24 7
40 7
45 7
60 9

This is likely a complete list. There are no others < 10^7.

Other numbers which are "record-setters" as the smallest n
with a particular square-denier:

n square-denier(n)
---------------------
184 11
280 13
364 16
1456 17
3124 19
5236 23
17185 25
25249 29
49504 37
233776 41
364144 43
775369 47
3864169 53
8794864 61

So, in some sense, these numbers could be considered pseudo-squares?






Tue Jan 15, 2002 7:35 pm

jbrennen
Offline Offline
Send Email Send Email

Forward
Message #4801 of 21107 |
Expand Messages Author Sort by Date

... Young man. At your age, at our age, young man... ... OK, I retract my part retraction too. ... As always, hats off to Marcel. ... Oh good. I've have a...
Phil Carmody
thefatphil
Offline Send Email
Jan 15, 2002
5:47 pm

... b that is a square-denier (yes, neologism) for n. ... (done without taking a square root, of course!) ... Cases of non-square n with smallest square-denier...
jbrennen
Offline Send Email
Jan 15, 2002
7:35 pm

... Hehe, I knew I'd be beaten to this. Hmmm, must buy laptop... Incidentally, what algorithm did you use? I'd guess a straight sieve would work (which would...
Phil Carmody
thefatphil
Offline Send Email
Jan 15, 2002
8:29 pm

... would work (which would be blazingly fast)? The CRT method seems to fan out too much to be practical. What range do you think you could practically search...
jbrennen
Offline Send Email
Jan 15, 2002
9:33 pm

May I try to summarize what has been found so far on this topic? (for all of us who have a hard time keeping up with you blazingly fast thinkers.) A. We're...
Hadley, Thomas H (Tom...
kctom99
Offline Send Email
Jan 15, 2002
9:33 pm

If you read msg 4790, there may be a slight misunderstanding involving the distinction between the quadratic residue concept and the Jacobi symbol used to...
grmulkey
Offline Send Email
Jan 18, 2002
11:20 am

... It appears that my generic sieve can't cope with non-prime bases in its filters. (i.e. the prime power bases). So I'm running at about 5% of my top speed...
Phil Carmody
thefatphil
Offline Send Email
Jan 17, 2002
10:05 am

... Well, I improved my sieve a bit, and I currently have a run rate of just over 20 million numbers a second, or about 7.5*10^10 / hour. This is on a Pentium...
Jack Brennen
jbrennen
Offline Send Email
Jan 18, 2002
8:24 am

... Given the choice, I always sieve on my 533MHz alpha. ... I have some crappy overheads that I need to get rid of per block so I've aimed my sieve at my 96K...
Phil Carmody
thefatphil
Offline Send Email
Jan 18, 2002
9:39 am

... hour. ... I bow before the master. I should go throw my sieve program into a bottomless pit, and study at the FatPhil school of sieving, I guess....
jbrennen
Offline Send Email
Jan 18, 2002
3:30 pm

... Note that 4790 had a bit of 2+2=5 logic in it. However, without that post, Jack and I would never have started hunting for the aberrant 5s! ... Absolutely....
Phil Carmody
thefatphil
Offline Send Email
Jan 18, 2002
12:37 pm

... 1) Use CRT as much as possible. (I could go to ~72 then ~130G/s by putting another prime or two in the CRT stage). 2) Saturate the pipelines for each tiny...
Phil Carmody
thefatphil
Offline Send Email
Jan 18, 2002
4:21 pm

OK, I think I understand more now about the Jacobi symbol (after reading more in the Prime Pages Glossary about it). ... You're right. Here's what I found: The...
Hadley, Thomas H (Tom...
kctom99
Offline Send Email
Jan 18, 2002
8:37 pm

... At last: the Eddington denial. ... But not all that close... David...
djbroadhurst
Offline Send Email
Jan 18, 2002
8:56 pm

... Don't be fooled, any composite based tests are not Jacobi symbols. They are the 'intersection' of two Legendres. If one fails, the composite fails. ... ...
Phil Carmody
thefatphil
Offline Send Email
Jan 18, 2002
10:15 pm

The only reference I saw addressing this question is in Cohen's "A Course in Computational Algebraic Number Theory", which states that a number n is a square...
jfribrg@...
Send Email
Jan 19, 2002
5:00 pm

The square detcection algorithm is in Cohen, section 1.7.2, page 39-40. Ron ... From: jfribrg@... <jfribrg@...> To: primenumbers@yahoogroups.com...
Ronald Hallam
ronhallam@...
Send Email
Jan 19, 2002
7:29 pm

... Absolutely. I put a smallish challenge to a guy on sci.math who came up with the same observation. Finding ones which are hard to factor was hard! I...
Phil Carmody
thefatphil
Offline Send Email
Jan 20, 2002
10:34 am

... Prime powers under 200 and a cherry on top! Someone beat me to the cherry, alas: http://www.ams.org/journal-getitem?pii=S0025-5718-96-00678-3 Oh dear -...
thefatphil
Offline Send Email
Jan 20, 2002
6:12 pm

... The values that Cohen uses are 64, 63, 65, and 11. 99% of non-squares fail ones of these tests. After this, an integer square root must be calculated. ...
Paul Jobling
paul_joblinguk
Offline Send Email
Jan 21, 2002
10:04 am

... Does he say why? It's obvious really: 64 is 'instant' But why not do 64 bits simultaniously, rather than just 6? - see my 4-clock-tick no-lookup-table...
Phil Carmody
thefatphil
Offline Send Email
Jan 21, 2002
11:38 am

... Because the rejection ratios are greatest in that order, as you say. Cohen suggests that it might be better to do it all in one go (save for the mod 64, ...
Paul Jobling
paul_joblinguk
Offline Send Email
Jan 21, 2002
11:45 am

... Yeah, but wouldn't you rather 'divide' it by 16777215 = 0xFFFFFF? Take 3 words (p,q,r) from memory and partition the bytes as follows into 4 24-bit...
Phil Carmody
thefatphil
Offline Send Email
Jan 21, 2002
7:47 pm

... I saw someone else (I think it was the GMP guys) recommend the idea for using 4 separate registers rahter than one massive 96-bit value requiring carries...
Phil Carmody
thefatphil
Offline Send Email
Jan 21, 2002
11:29 pm

... As I said in http://groups.yahoo.com/group/primenumbers/message/4855 when I first lambasted Henri's arbitrary choice of 11, <<< Therefore the number of...
Phil Carmody
thefatphil
Offline Send Email
Jan 22, 2002
6:43 am

... This was a typo I guess. 45045 was what I meant. Regards, Paul. __________________________________________________ Virus checked by MessageLabs Virus...
Paul Jobling
paul_joblinguk
Offline Send Email
Jan 22, 2002
9:53 am
 First  |  |  Next > Last 
Advanced

Copyright © 2009 Yahoo! Inc. All rights reserved.
Privacy Policy - Terms of Service - Guidelines - Help