Sieving (finding all X<=M so that X^2+1 factors into primes <= 761): First version: factor X^2+1 and test smoothness. takes 11,000 cycles per test. Improvements (gcd trick) accelerate method but still not good enough. Second version: adding logarithms (as described in earlier mail) and use priority queues. Takes 310 cycles. Tedious optimizations bring it down to 240 cycles. Inspection of the machine code shows the reschedule of the binary heaps eats most of the cycles. Third version: same but _discard_ priority queues. Careful but straightforward optimization bring method down to just over 11 cycles per test! Analyzing memory throughput and intructions involved: both reasonably close to peak performance. Any further speedup would need completely new ideas. Curious arccot relation (write [X] for arccot(X)): If [X] was exactly 1/X we'd have [X] = [X+1] + [X*(X+1)] (and trivially [N*X] = [N*(X+1)] + [N*X*(X+1)]) But [X] = 1/X -1/(3*X^3) +- ... and we have [K*N] = [(K+1)*N] + [K*(K+1)*N] - [Q(K,N)] (*) where Q(K,N):=K^2*(K+1)^2*N^3+(K^2+K+1)*N The relation depends on the factorization of the argument X. Contrast the well known [X] = [X+D] + [X+(X^2+1)/D] which depends on the factorization of X^2+1. Note that relation (*) gives different expressions for [K*N], [N*K], [1*(N*K)], and [(N*K)*1] Is relation (*) already known? Worth to be added on one of Eric's pages? The arccot connectedness of Q(K,N) is reflected in Q(K,N)^2 + 1 == ((N*K)^2+1) * (((K+1)*N)^2+1) * ((K*(K+1)*N)^2+1)