Skip to main content
Jan-Christoph Schlage-Puchta's user avatar
Jan-Christoph Schlage-Puchta's user avatar
Jan-Christoph Schlage-Puchta's user avatar
Jan-Christoph Schlage-Puchta
  • Member for 11 years, 5 months
  • Last seen more than a month ago
comment
How many integers divide a number that involves just three non-zero digits?
The first half of my answer didn't make much sense. I deleted it and expanded the second half.
revised
How many integers divide a number that involves just three non-zero digits?
As Dimitrov already noted, the first half of my answer did not make much sense. I deleted it and improved the second part. I just hope I got the computations right.
Loading…
awarded
comment
Divisor sums over values of binary forms of primes
For this range an upper bound sieve should suffice. The real quantity is smaller than the main term by a factor $\frac{\log x}{\log\log x}$, so loosing a constant does not matter. Hence we can replace the set of primes e.g. by all integers having only prime factors $\geq x^{0.01}$. To do so by Selbergs sieve you need asymptotics for the number of solutions of $a^2+b^2\equiv 0\pmod{n}$, $a,b,\leq x$, $q|ab$, where $n$ and $q$ satisfy $n<x$, $q<$x^{0.02}$, which looks doable.
comment
Is there an odd integer $x < 105$ for which it is known that $x \nmid N$, if $N$ is an odd perfect number?
For example, McDaniel (On the divisibility of an odd perfect number by the sixth power of a prime. Math. Comp. 25 (1971), 383–385) showed that an odd perfect number is either divisible by the sixth power of a prime, or it is not divisible by any prime $<100$. The proof is quite easy, once one has shown that if $n$ is not divisible by the sixth power of a prime, then $n$ is not divisible by some small prime, but getting there is pretty difficult.
comment
Is there an odd integer $x < 105$ for which it is known that $x \nmid N$, if $N$ is an odd perfect number?
There is a lot of literature proving the non-existence of odd perfect numbers satisfying certain additional restrictions. Practically all of them require some starting point of the form "One of these primes divides $n$" or "One of these primes does not divide $n$". Sometimes this starting point is easy to get (e.g. if you bound the number of distinct prime factors), but quite often getting the starting point is the most difficult part.
awarded
comment
Is there an odd integer $x < 105$ for which it is known that $x \nmid N$, if $N$ is an odd perfect number?
Cohen and Hagis proved that the largest prime factor of an odd perfect number is $>10^6$. Of course, the proof is indirect, so it begins with "Let $n$ be an odd perfect number with all prime divisors $\leq 10^6$...". Then a sequence of properties for $n$ are deduced, one of which reads "Lemma: $n$ is not divisible by 3, 5, 7, ..." . This Lemma was later taken out of context and cited as "Let $n$ be an odd perfect number. Then $n$ is not divisible by 3,5,7,...".
Loading…
answered
Loading…
Loading…
Loading…
Loading…
awarded
awarded
Loading…
awarded
answered
Loading…
comment
Can the Legendre symbol be calculated in polynomial time?
The overhead is not as small as it seems to be. In my experience a single "if" costs as much as 10-20 multiplications of 64 bit numbers. So checking what kind of shifts you have to perform and what sign you have to remember takes as much time as multiplying to 256 bit integers. Of course reciprocity will overtake Euler way before one can think of FFT multiplication.