Standard crank division by zero thread

[xilman]

Originally Posted by Don Blazys

What is a "raw count"?

It's one without any further processing and, in particular, no attempt to use your function which you've fitted to earlier data.

Paul

[xilman]

Originally Posted by science_man_88

according to my blazy function (not blazy2 that would take too long(that and my computer restarted last night so unless i look through my log file I'll never find it.) I get

(08:59)>blazy(2000000000000)
%1 = 1280724920347.099493640852596

in 0 ms.

and

(09:01)>blazy(10000000000000)
%2 = 6403626165691.467931734187920

also in 0 ms.

Ok, the true counts for these values are 1280724918033 and 6403626146905 respectively. The difference between the estimates you posted and the true counts are 2314 and 18786 respectively.

The fitted function is still quite close but it is starting to look like as if it over-estimates the counts at large values of its argument.

We should soon have counts as high as 4e13 and can test Blazys' hypothesis further.

Paul

[CRGreathouse]

Originally Posted by xilman

The fitted function is still quite close but it is starting to look like as if it over-estimates the counts at large values of its argument.

That was what it was looking like with my numbers, too. Still, the Ansatz looks right: the function behaves very much like

Best-fit coefficients:
c₁ = 0.640362740389
c₂ = -0.397518352268

Blazys:
c₁ = 0.64036274310
c₂ = -0.40011254372

[akruppa]

Originally Posted by xilman

Mail me if you would like a copy of the code for comparison

I've deleted mine right after my posting.

[science_man_88]

Originally Posted by xilman

We should soon have counts as high as 4e13 and can test Blazys' hypothesis further.

Paul

(10:40)>blazy(4*10^13)
%16 = 25614507193299.7888452548097563947823880

this is what I get.

[science_man_88]

once you prove if it's accurate you might want this one:

(17:17)>blazy(4*10^100000000)
%18 = 2.56145097238337059635728678312415503847 E100000000
(17:17)>##
  ***   last result computed in 32,156 ms.
(17:18)>

[R.D. Silverman]

Originally Posted by CRGreathouse

That was what it was looking like with my numbers, too. Still, the Ansatz looks right: the function behaves very much like

Best-fit coefficients:
c₁ = 0.640362740389
c₂ = -0.397518352268

Blazys:
c₁ = 0.64036274310
c₂ = -0.40011254372

May I suggest that some actual mathematical analysis might be
beneficial, rather just doing a 'least-squares' fit to the data?

Counting these numbers (as already pointed out) is easy with a sieve.

We can get a very easy (and very very sharp!) estimate for the
total number of polygonal numbers less than (say) B via
Euler-Maclauren summation. We have the counting function
for r-gonal numbers:

c(r,n) = 1/2n ( (r-2)n - (r-4))

So just solve c(r,n) < B for n as a function of r and B (a trivial
quadratic equation), then do a Stieltje's integration over r.

But this will give multiple counts of some elements since there are many
duplicates.

Fortunately, the technique for getting a sharp estimate of duplicates
in a sieve was presented many years ago by DeBruijn in a paper
called something like "On the number of uncancelled elements in the
Sieve of Eratosthenes". This paper showed how to get a good estimate
of the duplicate hits in a sieve through the use of the Buchstab function.
This function is very oscillatory and is given by a differential-delay
equation similar to the Dickman's functional equation.

It's been many (~25?) years since I read this paper. I will try to dig
it out of my archives an re-read it. I suggest that reading this paper
and applying its techniques is a requirement for anyone who wants to
proceed further.

[CRGreathouse]

Originally Posted by R.D. Silverman

May I suggest that some actual mathematical analysis might be
beneficial, rather just doing a 'least-squares' fit to the data?

The purpose of the fit was to show that, even at the second or third decimal place, Blazys' (second) constant appears to be off.

But yes, I would like to analyze this mathematically (as, indeed, I was discussing yesterday with Paul). My initial attempts were based on pairwise intersections between forms, but the cancellation is too high with that method. My next thought was do a Legendre sieve-type calculation -- count contributions for all orders but cancellations only for small orders, bounding the overlap from higher orders. I'm not sure if this can extract enough information.

I'll look into the paper you suggest, but at first glance it's not clear how to apply it to the problem at hand. Hmm... we *do* have a (small-sieve) equivalent of Buchstab's identity, so I guess it's not hopeless.

Originally Posted by R.D. Silverman

Counting these numbers (as already pointed out) is easy with a sieve.

Sure, I've already logged a few dozen core-hours sieving on the problem. I had meant to code an improved sieve today (based on an idea stolen from Tomás Oliveira e Silva) but I've been working on other things.

Originally Posted by R.D. Silverman

We can get a very easy (and very very sharp!) estimate for the
total number of polygonal numbers less than (say) B via
Euler-Maclauren summation. We have the counting function
for r-gonal numbers:

c(r,n) = 1/2n ( (r-2)n - (r-4))

So just solve c(r,n) < B for n as a function of r and B (a trivial
quadratic equation), then do a Stieltje's integration over r.

That gives way too much overlap to be useful. All numbers = 15 mod 30 are polygonal of order 3 and 5, so it overcounts by at least n/30, which is *huge* compared to the precision to which we've empirically determined the coefficients.

Originally Posted by R.D. Silverman

Fortunately, the technique for getting a sharp estimate of duplicates
in a sieve was presented many years ago by DeBruijn in a paper
called something like "On the number of uncancelled elements in the
Sieve of Eratosthenes". This paper showed how to get a good estimate
of the duplicate hits in a sieve through the use of the Buchstab function.
This function is very oscillatory and is given by a differential-delay
equation similar to the Dickman's functional equation.

I have some old code I could dust off for computing Dickman's function, perhaps that could be adopted for the relevant function here. But I'm still not clear on how to adapt the techniques of the paper to this not-entirely-similar problem.

[R.D. Silverman]

Originally Posted by CRGreathouse

The purpose of the fit was to show that, even at the second or third decimal place, Blazys' (second) constant appears to be off.

But yes, I would like to analyze this mathematically (as, indeed, I was discussing yesterday with Paul). My initial attempts were based on pairwise intersections between forms, but the cancellation is too high with that method. My next thought was do a Legendre sieve-type calculation -- count contributions for all orders but cancellations only for small orders, bounding the overlap from higher orders. I'm not sure if this can extract enough information.

I'll look into the paper you suggest, but at first glance it's not clear how to apply it to the problem at hand. Hmm... we *do* have a (small-sieve) equivalent of Buchstab's identity, so I guess it's not hopeless.



Sure, I've already logged a few dozen core-hours sieving on the problem. I had meant to code an improved sieve today (based on an idea stolen from Tomás Oliveira e Silva) but I've been working on other things.



That gives way too much overlap to be useful. All numbers = 15 mod 30 are polygonal of order 3 and 5, so it overcounts by at least n/30, which is *huge* compared to the precision to which we've empirically determined the coefficients.



I have some old code I could dust off for computing Dickman's function, perhaps that could be adopted for the relevant function here. But I'm still not clear on how to adapt the techniques of the paper to this not-entirely-similar problem.

I am at home, recovering from surgery and the paper is in my office.
It will be a few days before I can retrieve it. The paper is quite old
and I doubt whether it is available on the net.

[science_man_88]

Originally Posted by R.D. Silverman

I am at home, recovering from surgery and the paper is in my office.
It will be a few days before I can retrieve it. The paper is quite old
and I doubt whether it is available on the net.

I hope you get tons of rest. I presented a slow code in post 54 ?

blazy2(x)=y=[];for(k=3,x+1,for(n=3,x+1,if((1+k*n*(n-1)/2-(n-1)^2)<(x+1),y=concat(y,[(1+k*n*(n-1)/2-(n-1)^2)]),break(1))));y=vecsort(y,,8);return(#y)

[CRGreathouse]

Originally Posted by R.D. Silverman

I am at home, recovering from surgery and the paper is in my office.
It will be a few days before I can retrieve it. The paper is quite old
and I doubt whether it is available on the net.

Fortunately, it seems to be online, age notwithstanding:
http://alexandria.tue.nl/repository/...les/597489.pdf