Timeline for Number of divisors of an integer of form 4n+1 and 4n+3
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 22, 2011 at 5:47 | comment | added | Gerhard Paseman | Unfortuately, my "best" attempt was pretty poor. While the number of factors of the form 4k+3 can be computed (and may/may not be equivalent to factorizing the number), it is not automatically floor(d/2) for d the number of divisors of n, nor is 0 always the answer. One needs to know quite a bit more to determine the precise number of factors, especially the number of factors f such that f is 4k+1 but also that any factor of f also is 1 mod 4. Gerhard "Shot From Hip And Missed" Paseman, 2011.03.21 | |
| Mar 17, 2011 at 19:39 | comment | added | Douglas Zare | The original question appears nontrivial. It does not say you are required to list the divisors, it says that is an unsatisfactory method. The difficulty is not the very easy step of going from the prime factorization to the counts. If you could prove that there is no way to get the counts without being able to obtain a factorization, that would be interesting. | |
| Mar 17, 2011 at 15:19 | comment | added | Gerhard Paseman | I am answering the original question as best as I can, Douglas. If the poster wants divisors without factoring, I can only think of puttiing the work of factoring off on someone else. Whom else? I don't know, and indicated as much in my signature. Gerhard "Knows Way To San Jose" Paseman, 2011.03.17 | |
| Mar 17, 2011 at 13:28 | comment | added | Douglas Zare | Factorization is hard, and I do not view it as significantly easier than writing out a list of all divisors. You say consult two oracles. I don't grant you those oracles as building blocks. Is it easier to get that information than factorizing $n$? As "unknown" pointed out, some types of information are expected to be about as hard as factorization. | |
| Mar 17, 2011 at 6:07 | comment | added | Gerhard Paseman | Actually, there is a way for odd n which does not involve full factorization. First, consult an oracle which (correctly) gives you the number of factors of n. Second, consult another oracle which (correctly) tells you if at least one of the factors is of the form 4k+3. Then the number of factors of the form 4k+3 will be 0 or floor(d/2), where d is the number of divisors of n, and where you need the second oracle to determine which. For even n, keep dividing by 2 first, and record the number of such divisions. Gerhard "Ask Others Directions to Delphi" Paseman, 2011.03.16 | |
| Mar 17, 2011 at 5:59 | comment | added | Gerhard Paseman | I don't need a list of all the divisors, just a list of all the prime divisors (with multiplicity). That is tantamount to factoring the number, but is not the same as computing the list of all divisors. I suggest a method that does not need the list of all the divisors. (Also, I need to change a q to a p). There may be a method to compute quickly the parity of the number of 4k+3 divisors, but the answer is still going to be 0 or about half the number of divisors of the given number n, assuming n is odd. Gerhard "Ask Me About System Design" Paseman, 2011.03.16 | |
| Mar 17, 2011 at 2:26 | comment | added | David Hansen | How are you going to list all the divisors without factorizing? A complete list of divisors + AKS = prime factorization, so I don't think you can avoid this. | |
| Mar 17, 2011 at 2:02 | comment | added | pranay | Thanks, but i was thinking if there exists any method not involving factorisation.. | |
| Mar 17, 2011 at 1:58 | history | answered | Gerhard Paseman | CC BY-SA 2.5 |