Impact
~9k
people reached
- 0 posts edited
- 0 helpful flags
- 19 votes cast
Feb
1 |
awarded | Popular Question |
Dec
21 |
comment |
Arithmetic functions associated with Hurwitz Zeta function raised to arbitrary complex powers, $\zeta(s,q)^z$ for $q \in \mathbb{N}$?
Does this prove, absolutely, that there can be no such $f_{q,z}(n)$, specifically for $q \in \mathbb{N}$? Or just that the usual methods can't be used to find such a function, and that it won't resemble the tidy definition for $d_z(n)$? |
Dec
20 |
asked | Arithmetic functions associated with Hurwitz Zeta function raised to arbitrary complex powers, $\zeta(s,q)^z$ for $q \in \mathbb{N}$? |
Sep
24 |
awarded | Autobiographer |
Jul
2 |
awarded | Curious |
Apr
22 |
asked | Can the generalized divisor summatory function $D_z$ be expressed explicitly in terms of Zeta Zeros? |
Apr
1 |
awarded | Notable Question |
Dec
13 |
awarded | Tumbleweed |
Oct
23 |
asked | A generalization of alternating series involving modulus? |
Jun
25 |
awarded | Promoter |
Jan
14 |
revised |
Any published references for this $O(n)$ time, $O(n^\epsilon)$ space identity for the count of primes?
Added more justification and examples for the time and space bound claims. |
Dec
20 |
comment |
Any published references for this $O(n)$ time, $O(n^\epsilon)$ space identity for the count of primes?
Charles: I suppose I did mean $O(n^\epsilon)$. Anyway, in neither implementation are any values memoized. This is especially easy to see in the first C implementation I linked to. If you skim the 25 lines of code of the actual algorithm, you can see it's literally transcribing the identity I'm asking about verbatim. No tricks or cleverness (aside from specializing D_1 for constant time speed improvement). Aside from pushing functions onto the stack to a depth of $\log_2 n$, no memory is ever allocated. Also notice my edit; sorry about that. |
Dec
20 |
revised |
Any published references for this $O(n)$ time, $O(n^\epsilon)$ space identity for the count of primes?
Fixed an error in the identity - a specific specialization is required for it to work. |
Dec
20 |
revised |
Any published references for this $O(n)$ time, $O(n^\epsilon)$ space identity for the count of primes?
Fixed Memory Bound notation |
Dec
20 |
revised |
Any published references for this $O(n)$ time, $O(n^\epsilon)$ space identity for the count of primes?
Added some clarifying references |
Dec
19 |
comment |
Any published references for this $O(n)$ time, $O(n^\epsilon)$ space identity for the count of primes?
Oh - epsilon. Negligible. Probably $\log n$ or thereabouts, because the recursive depth of $D_{k,a}(n)$ grows at roughly $\log n$ Essentially it doesn't use any memory at all for practical purposes. |
Dec
19 |
asked | Any published references for this $O(n)$ time, $O(n^\epsilon)$ space identity for the count of primes? |
Jun
22 |
accepted | The relationship between the Dirichlet Hyperbola Method, the prime counting function, and Mertens function |
Jun
22 |
comment |
The relationship between the Dirichlet Hyperbola Method, the prime counting function, and Mertens function
Thanks Terry. Given that my question was a bit vague, this is some great stuff for me to chew on. |
Jun
8 |
awarded | Enthusiast |