156 reputation
313
bio website icecreambreakfast.com/…
location Pittsburgh, Pa
age
visits member for 3 years, 9 months
seen 13 hours ago
I'm highly interested in algorithms for computing arithmetic summatory functions, Linnik's identity, arithmetic summatory functions generally, and especially the role of divisor-style functions in those spaces.

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
Dec
6
asked In this prime counting identity, can this limit of a sum be expressed as integrals?
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
Jun
6
revised Logarithmic Integral of n^Zeta Zeroes and certain nested sums of the fractional part function
Clarified question further to highlight my focus on the divisor summatory function
Jun
6
comment Logarithmic Integral of n^Zeta Zeroes and certain nested sums of the fractional part function
That exhausts my ideas, I think. So that's the core of my "other techniques" question - 1) are there other ways of expressing $H_k(n)$ (or $D_k(n)$) that lead to any interesting observations in my (4)? And particularly, are there any clever ideas for combining any of those alternative expressions with symmetries between, say, $H_2(n)$ and $H_3(n)$ and $H_4(n)$ and so on, which all jump in ways that share some connections?