[Algorithm] Sum of Primes < 1000000

  • Thread starter Luc The Perverse
  • Start date
J

John Ersatznom

Simon said:
No, I didn't. That's what I'm trying to say.

Then you either try again or give up -- what more is there for me to
say? You might also examine my other response to this thread today. In
any event, there is no call for going around publicly suggesting that
anyone else's arguments are "questionable" or similarly just because you
didn't happen to understand them.

Curiously, my earlier post to this thread (that you'd responded to) is
gone. My newsserver claims a 15 day retention and it's only a week old,
which means somebody forged a cancel. It wasn't you, I hope. (If it was,
it's ironic that you quoted much of it in your reply.)
 
J

John Ersatznom

Lew said:
Over the last thirty or so years, I have seen many projects where we
were told "we can always refactor it later", but later were told, "we
are not going to refactor given the investment in the existing codebase,
besides it works, doesn't it?"

As a practical matter it is almost impossible to get management buy-in
to throw away existing code no matter how terrible...(They always looked
so sad when I told them, "Port Steve's code? I never even looked at
Steve's code; I just rewrote the application from the specification.")
The investors pulled out all their money from the company two weeks
later (possibly for unrelated reasons). Welcome to the future.

There has to be an awful lot of pain before there is buy-in for
refactoring, and often not even then.

Wash your hands of it. If management says "we can always refactor it
later" get that in writing or on tape. If later it won't scale, point
out the earlier discussion (for which you have documentation). Also note
that they did invest money in the existing code, and they then got
however-many years of use out of it before their needs outgrew that
code. Replacing it isn't throwing away the investment, it's making a new
investment after an earlier one has paid off about all it's going to.

If they still don't see the light, wash your hands of it. Say "OK" and
do whatever. If the company goes kaput, gets scammed and goes kaput, or
whatever, well, you did your duty of warning them and they did their
duty of actually making the call. They got it wrong but not for lack of
information; it's not your fault. If you have the skills, you can find
another job and maybe one where your expertise will be better
appreciated. As for the company that goes under, well, that's Darwinism
at work. If the management can't find new work after it does, well,
that's probably also Darwinism at work. ;)
 
S

Simon

John said:
Yes; the fact that he was accusing me of being bad at math.

I wasn't accusing you, I was analysing your arguments.
Well, to start with, he basically accused Wikipedia of having the
integral of ln(x) wrong.

- You said: "integral of log x is log x - x"
- Wikipedia correctly says
(http://en.wikipedia.org/wiki/List_of_integrals_of_logarithmic_functions)
"int ln(cx) dx = x * ln (cx) - x"
For our case c=1, this is the same as I said ("Furthermore, the integral of log
x is not lox x - x, but rather x * log x - x. )
He also correctly stated that an average of a set exceeds 1/4 the size
of the set, but thereby was trying to imply that the optimization sucked

I didn't say that anything sucked. What optimisation? Starting with the square?
We all know that this does not suck. It is standard.
because something was therefore O(N) in the total number range instead
of O(log N).

I was saying "something was O(N)"? What is something? Do you mean Omega(N)?
The set was of primes, and the size of that is O(log N), so
1/4 of that is O(log N).

The average over any set of positive integers of cardinality k is at least
Omega(k). You said: "The average prime from this set will be O(1)". This is
obviously wrong unless the set contains only O(1) elements.
He actually ends up proving the weak result
that the size of the average prime less than N is *at least* O(log N)
(not ruling out O(N) or whatever);

That wasn't a weaker result, it was a counter argument to your bogus claim.
Furthermore, something cannot be *at least* O(log N). It can only be *at least*
Omega(log N). You should really learn the terms.
I had gotten the stronger result that
the size of the average prime *was* only O(log N).

You are saying the average prime below N is O(log N)?
There are O(log N) primes below N. At least one of these primes is at least N/2.
Even if we ignore the contribution of all other elements in this set, this
single prime alone implies an average of at least Omega(n/log n).


I have the impression that you are trying to look at the set {1,...,N} and take
the average only over the primes in this set, whatever that means. If that is
what you are trying to do, you really should write that down more precisely.
Still, it would be unclear what this would contribute to your reasoning.
The reasoning in a nutshell:

Algorithm to build sieve up to N as I stated it has three parts. Loop
until sqrt(N) (O(sqrt(N)). For each p reached that's not gotten marked
composite earlier, loop from p^2 until N step p. The number of these
loops is O(P), P the number of primes up to sqrt(N). The length of a
given one is O(N/p). Turns out P is O(log(sqrt(N)) = O(1/2 log(N)) =
O(log(N)), so this loop is O(log(N)*X) where the average length of a
loop is O(X). What is the average length of a loop?

It's O(N/p) of course, for the average choice of p.

Note: You cannot just argue over averages and then multiply with the number of
iterations. In general, such arguments fail.
Primes are
logarithmically distributed (P is O(log(N)) above) so the average p is
going to be small fairly independently of the range. It's hard to be
sure it's O(1) though. The average is the sum divided by the total
number. The sum of the primes, the way they are logarithmically
distributed, could be approximated by the integral of the logarithm. (It
might actually be better now I think of it to integrate N/p -- N*(1/2 +
1/3 + 1/5...) looks like N times an exponential decay function, whose
integral is itself and which is clearly O(1))

Clearly?

1/2 + 1/3 + 1/5 + 1/7 + 1/11 ...

is O(1)? You should read:
http://mathworld.wolfram.com/HarmonicSeriesofPrimes.html

It approaches ln ln N.
I concluded that the average length of the loop is bounded by O(N),

You need this long argument to conclude that the average length of a loop that
starts above 1, has a step size of more than 1 and ends at N is bounded by O(N)?
Wow.
and
the whole algorithm by O(N log N). If it's actually N log log N or can
be made such, so much the better.

It's a bit hard to understand why you need so much reasoning for this simple
bound for which already two independent arguments (each of which fit into two
lines) have been given.

BTW: Now that we know that the harmonic series of primes grows as O(ln ln N),
this proves that the total time is O(N * log log N).

Cheers,
Simon
 
S

Simon

John said:
Curiously, my earlier post to this thread (that you'd responded to) is
gone. My newsserver claims a 15 day retention and it's only a week old,
which means somebody forged a cancel. It wasn't you, I hope. (If it was,
it's ironic that you quoted much of it in your reply.)

You are suspect me of cancelling your article? Now it's getting weird. Why
should I do that? It is still available on my newsserver, as it is on Google groups.

Cheers,
Simon
 
C

Chris Uppal

[Since this thread seems to have come alive again...]
Apart from that, from your other post I saw that you have used a different
argument to obtain the n log n upper bound.

- Your argument: There are only log n primes below n and each iteration
takes time at most n.

I can't find the post where that argument is made, but I think it's wrong;
there are O(n/log(n)) primes up to n which would give an estimate of O(n^2 /
log(n))

- My argument: Consider the iteration in which we erase prime i. We erase
n/i composite numbers. In total, we need time

sum(i=1..n) n/i
= n * H(n)
= O(n * log n)

(Here, H(n) is the n-th harmonic number.) Can we combine both arguments to
obtain an upper bound below n * log n?

You can weight the terms in the sum by the probability that each i is prime.
That (as I understand it) is approximated by 1/log(i).

Also you can reduce the upper bound on i to sqrt(n), which only affects the
constant factors in your formula, but might not "vanish" in the same way with
the weighting applied.

Still, some Googling reveals that it is possible to get the time down to
n * log log n.

Sadly, I have no idea whether the weighted sum agument yeilds that formula...

-- chris
 
L

Lew

John said:
Then you either try again or give up -- what more is there for me to
say? You might also examine my other response to this thread today. In
any event, there is no call for going around publicly suggesting that
anyone else's arguments are "questionable" or similarly just because you
didn't happen to understand them.

Isn't it fair to say that academic discourse is only possible when at least
one party calls another's reasoning into question? Otherwise it's merely
lecturing. If you aren't ready to have your ideas questioned, it is not yet
time to reveal them.

As to understanding, Simon's posts indicate at least a firm general
understanding of your comments, so lack of expertise seems not to be an issue.
His specific points may be wrong, and he did have specific questions, but his
arguments are not so easily dismissed by a blanket condemnation of his maths
chops. You should examine his claims on a peer level; the ad hominem approach
will not be effective.

I am here to say that both of your arguments are questionable. But I'm only
saying that because so far I don't happen to understand them completely.

- Lew
 
S

Simon

Chris said:
[Since this thread seems to have come alive again...]
Apart from that, from your other post I saw that you have used a different
argument to obtain the n log n upper bound.

- Your argument: There are only log n primes below n and each iteration
takes time at most n.

I can't find the post where that argument is made, but I think it's wrong;
there are O(n/log(n)) primes up to n which would give an estimate of O(n^2 /
log(n))


You are right, I misread Patricias post. She wrote: "I was not allowing for only
doing the inner loop for primes." so I asked myself how this can help to get the
bound down from O(n^2) to O(n log n). That would work if the number of primes
was O(log n), so I prematurely thought that might be Patricias argument. But it
is, of course, nonsense. Sorry.

Cheers,
Simon
 
S

Simon

Simon said:
You are saying the average prime below N is O(log N)?
There are O(log N) primes below N. At least one of these primes is at least N/2.
Even if we ignore the contribution of all other elements in this set, this
single prime alone implies an average of at least Omega(n/log n).

Forget this argument, it is nonsense :)
This one is better:

There are Omega(N/log N) primes between N/2 and N each of which has size at
least N/2. Furthermore, there are O(N/log N) primes below N/2, so the average is
at least

c1 * N/2 * N / log N
------------------- = N * c1/(2*c2)
c2 * N/log N

for suitable constants c1 and c2.

Cheers,
Simon
 
J

John Ersatznom

Simon wrote:
[snip most]
That wasn't a weaker result, it was a counter argument to your bogus claim.

I'm not going to argue with you if all you're going to do is sit here
and insult me.

[Remainder of condescending BS snipped]

Good day.
 
J

John Ersatznom

Lew said:
As to understanding, Simon's posts indicate at least a firm general
understanding of your comments, so lack of expertise seems not to be an
issue. His specific points may be wrong, and he did have specific
questions, but his arguments are not so easily dismissed by a blanket
condemnation of his maths chops...

The simple fact that he's disputing what I said instead of nodding and
moving on is evidence enough that he didn't properly understand what I
wrote.
 
L

Lew

John said:
The simple fact that he's disputing what I said instead of nodding and
moving on is evidence enough that he didn't properly understand what I
wrote.

Of course it is.

- Lew
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top