It Begs The Question
Hey…I'm just saying… And while we're at it, why are you defending them?

Epilogue To The Composite Chronicle

Math Mystery Epilogue

 

This post is a kind of “stream of consciousness” epilogue to the Math Mystery Project; aka the Harmonic Series of Composites project. It’s a “story” of sorts; an additional chronicling of the “ending” of the project. Anyway, none of what follows will make any sense at all until/unless you’ve read the first 3 “parts” of the “Math Mystery” story. Here’s the links if you want to get started.

1 https://itbegsthequestion.com/ an-actual-math-mystery/

2 https://itbegsthequestion.com/ math-mystery-followup/

3 https://itbegsthequestion.com/ math-mystery-wrap-up/

Ok, we’re back. As you probably noticed, this “project” ended up being something completely different than what it started out as. That’s not uncommon either with the projects or with life in general (duh). We start out investigating something, notice something “odd” or interesting, or shiny, and then it’s off in another direction; sometimes a bunny trail into the weeds but sometimes something meaningful and fascinating and worth remembering.

Anyway, at the end of Part 3 of the Math Mystery, I decided to find and email some professional mathematicians to see what they thought of what was “discovered.” I’ve not heard back from the first 2 yet but here is the email I sent to them (btw I am including this “first” email and parts of some others and the responses in order to document what was being thought at the time…. a personal historical log. Ooh! A “phlog!” Anyway, here’s the first email to two pros:

Dear Mr. Roelandts,

I am hoping you can solve a problem for me (or direct me to a doc that will).

π(n) is the count of primes in 1..n (the prime counting function)
let Sp be the Harmonic Series of Primes thru n
(1/1 + 1/2 + 1/3 + 1/5 + … 1/p)
let Sn be the Harmonic Series thru n
(1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … 1/n)

Then it’s my conjecture that:

ln(π(n)) + Sp ~ Sn

In words:

The log of the number of primes
plus
the sum of terms for the Harmonic Series of Primes
asymptotically approaches
the sum of terms for the “vanilla” Harmonic Series
If we manipulate the above formula we will get
Sp ~ ln(ln(n))
which we see a lot.
 —
In addition, if we actually perform the calculations
(at least thru n = 1 billion using doubles in a C# program)
the formula appears to hold water… but why? Why should π(n) be part of
the relationship between Sp and Sn? Why should π(n) be part of the relationship
between the Harmonic Series and the Harmonic Series of Primes?
 —-
Also see my blog article about the above at
Be advised that I am a rank amateur (capital R) but try as I might, I can’t find any articles or papers about this. What am I missing (if anything)?
Thanks in advance,

 

 

I also copied the above email to a friend of mine in California (JGM) and here is what transpired:

Gerry – I sent your email to a mathematics friend and this is what he said

looks like a number theory cleverness of Ramanujan (encouraged by Hardy)”

Note… emphasis is mine above.

To which I responded

I don’t know what that means. Anyway, I can see WHAT the
answer is both experimentally via computer and by doing the
math (algebra 1). It’s way way simple. Nothing
clever going on. I’m too much of an amateur to be clever. It’s
just that I can’t fathom WHY the log of the count of the primes
in the series would/should be related to the series “value” (the
sum). And I can’t fathom WHY there seems to be no significant
associated literature that I can find about this series (the
Harmonic Series of Composites aka Sum of Reciprocals of
Composites). Is Google trying to hide the answer from me? Uh
oh… I’m starting to connect conspiracy dots that don’t exist!!!
WAIT! What’s that noise!? OH NO!! There’s a black
escalade outside!! Gotta go. Just enough time to click on
SEND.
gerry

 

Then I googled “cleverness of Ramanujan” as mentioned above and found out what they were (presumably) talking about so I wrote back to JGM.

John,
Thanks to google I now get the “cleverness of Ramanujan” reference which I’ll take as a compliment though (largely?) maybe undeserved. Here is a link
https://www.wired.com/2016/04/who-was-ramanujan/

The wired magazine article linked to just above contains the following (emphasis below is mine).

Again, they began unpromisingly, with rather vague statements about having a method to count the number of primes up to a given size. But by page 3, there were definite formulas for sums and integrals and things. Some of them looked at least from a distance like the kinds of things that were, for example, in Hardy’s papers. But some were definitely more exotic. Their general texture, though, was typical of these types of math formulas. But many of the actual formulas were quite surprising—often claiming that things one wouldn’t expect to be related at all were actually mathematically equal.

btw, the Wired Magazine article referenced above was written by Stephen Wolfram. You may already know about him but if not, just google him (and prepare to be amazed).

btwbtw with regard to “often claiming that things one wouldn’t expect to be related at all were actually mathematically equal”  ……. It has VERY often been my experience that what often shines a bright light on relationships of “number stuff” are the results of actually doing computations… BILLIONS and BILLIONS of computations (we need to write programs for this!). Then analyzing and comparing the results (the numbers) using things like logs (which often plays a role in number theory) and using a good scientific calculator ( like the one that comes with Windows, or Google’s (just type “calculator” in the address bar of the Chrome browser)). All this just to help us “see” relationships. Of course, we need to have a feel for what we may want to compare and then we need to actually write the code to compute that stuff. Then the results will hint that we need some additional result which we dutifully add to the code… rinse and repeat. Of course, not every number computed will yield interesting results so we need to be prepared to “waste” many hours of effort writing and revising these programs. And keep in mind… we don’t get paid for this shit.

btwbtwbtw… the mathematicians of the past would very often do the same thing (perform gazillions of computations) and for the same reasons; but they did it by hand!… when paper was not easy to come by! Can you imagine what THEY would have thought, and given, to have a computer!?

Time to go… the black escalade is back.

gerry

So the above email chain is what I was thinking at the time. Then about a week later while googleing “harmonic series of composites” and related terms, I ended up on the OEIS web site and finding its founder, Neil Sloane.

IMPORTANT! Follow these links
to learn about OEIS and Neil Sloane:

So who’s Neil? And what is OEIS?

Science News https://www.sciencenews.org/article/pattern-collector

Wired Magazine Meet the Guy Who Sorts All the World’s Numbers in His Attic

The Guardian  https://www.theguardian.com/science/alexs-adventures-in-numberland/2014/oct/07/neil-sloane-the-man-who-loved-only-integer-sequences

For OEIS site, see —->> https://oeis.org/

and for my “contribution” to humanity see

https://oeis.org/search?q=A296358&language=english&go=Search

 

So I emailed Mr. Sloane to see what a recognized expert had to say about all this Harmonic Series of Composites stuff.  The email and his response follows:

Dear Mr. Sloane,

I am hoping you can help to solve a (simple?) series related problem for me (or direct me to a document that will). I can’t remember how I arrived at your name as a likely candidate for helping but it (of course) involved numerous google searches that eventually landed me on OEIS and one of its pages:

https://oeis.org/wiki/Talk: Harmonic_series_of_the_ composites

That page did not help directly but with just a few clicks around OEIS I stumbled on you. Anyway, with all that said, here is the short story… i.e. “Just the problem” as Sgt Joe Friday would say.

The two most “famous” series are the “vanilla” Harmonic Series, and of course, the Harmonic Series of Primes. The shorthand/symbols I use for these series is Sn and Sp (S for Series, n for natural numbers, and p for primes). When we go to infinity the

vanilla Harmonic Series ~ Ln(N)
and the Harmonic Series of Primes ~ Ln(Ln(N))
or…
Sn ~ Ln(N)
Sp ~ Ln(Sn)     or,    Sp ~ Ln(Ln(N))

We see the above in a lot of places.

But what about the third leg of the Harmonic Series “Triad?” What about the Harmonic Series of Composites ( we’ll call it Sc )? We find references and extensive literature all over the internet about the vanilla Harmonic Series (Sn ) and about the Harmonic Series of Primes (Sp) but the number of references to the Harmonic Series of Composites is just about nil! Why? Especially when its “value” is so interesting!!! And this brings us to the main points of this whole discussion.

1. What is the value of Sc ?
2. Why?

So what is its value? Of course, when we take all of the primes (p) away from the natural numbers (n) we are left with just composites.
Sc = Sn – Sp

Let’s massage the above a little and we’ll get…

Sn = Ln(N) and Sp = Ln(Ln(N))
so…
Sc = Ln(N) – Ln(Ln(N))

Here is where the magic happens with a little log arithmetic

Sc = Ln( N / Ln(N))
AND Note that … N / Ln(N) is the prime counting function π(N) so…
Sc = Ln(π(N))

or, said in words,
The Harmonic Series of Composites (aka Sc )
approaches the log of the number of primes in N as
N → infinity!

Note that experimental results (computations) support the above at least thru N = 1 billion. You will see this (and more) if you read the related blog articles (links are further down).

With all that said, some questions…  Did I miss something? Did I make some bone-headed mistake along the way?
Why don’t I find any literature about any of this? And, do you know of any literature/documents that cover the Harmonic Series of Composites?
I am Especially looking for an “intuitive” reason for WHY the log of the count of primes should have anything to do with the value of the Harmonic Series of Composites.

Thanks for any insights or other information you may have.

Gerry

P.S. Below are 3 links to a 3-part “story”/ history about all of this on my blog if you are interested. And once again, thanks for any insights you might have on the above.

1 https://itbegsthequestion.com/ an-actual-math-mystery/
2 https://itbegsthequestion.com/ math-mystery-followup/
3 https://itbegsthequestion.com/ math-mystery-wrap-up/

Mr. Sloane replied to the above email with this response (again, emphasis is mine).

Dear Gerry,
I agree with your estimate for Sum_{k=1..n} 1/composite(k).

Although the OEIS has many similar sequences of fractions – here is a list:
Sum 1/n: A001008/A002805, Sum 1/prime(n): A024451/A002110 and A106830/A034386, Sum 1/nonprime(n): A282511/A282512 –

it did not have that one. We did have the successive numerators (A282511)
but not the denominators, so I created A296358 for them (actually the denominators of Sum 1/nonprimes, A282512, are essentially the same sequence). So Sum 1/composite(n) is now A282511/A296358. I then added your interesting comment about the asymptotics to A296358. Although it is easy to prove, it is a nice observation, and I had not seen it before.
Thanks for writing.

Neil Sloane

 

Easy and simple are big pluses in math. And, the man who has seen it all in the world of integer sequences hadn’t seen this one! So it turns out that I was not crazy!! And he agrees with my proof. But… But… he did not hazard a guess as to WHY π(N), or more specifically, Ln(π(N)) should play a role in the value of the Harmonic Series of Composites… But it does… and it is! Once again, it appears to be another case of what was said in the Wired Magazine article about Ramanujan:

things one wouldn’t expect to be related at all were actually mathematically equal.”

So Mr. Sloane created my own entry/page in OEIS. It’s

http://oeis.org/search?q=A296358&language=english&go=Search

As said in the Guardian article

It is also a badge of honour to get a sequence accepted – although Neil and the administrators tend to be very generous in their selection criteria. Still, you need to think up something that hasn’t been thought up before!”

and…

Anyway… The “Mathematical equivalence” discovered during this project was and IS VERY surprising and unexpected.

Sc = Ln(π(N))

And it’s amazingly simple and easy to prove as Mr. Sloane will attest to. And one of the biggest surprises (and mysteries) is that, as far as I can tell, it’s been essentially unknown!… Even to Mr. Sloane! And just as surprising is that it all started with some unexplained notes on a wrinkled piece of notebook paper stuffed into a remote corner of an IKEA bookshelf! Life can indeed be VERY mysterious.

I wanted to remember all this for a long time which is why I spent the hours documenting it above, and in the first 3 articles.

 

The End

 

 

 

 

 

No Comments on Epilogue To The Composite Chronicle
Categories: Uncategorized

Math Mystery Wrap Up

If you haven’t already done it, you will need to read the following 2 articles to make total sense of this one.

A Math Mystery       and        A Math Mystery Follow Up

And after reading this article there’s a 4th and final one

Epilogue – Chronicle of Composites Project

 

Let’s just start with the formula for the “vanilla” Harmonic Series. 

Then massage it in 4 simple steps and see where it takes us!

Note:  in the following    is the value of the largest denominator in the “vanilla” Harmonic Series  (Sn )  and

in the Harmonic Series of Primes  (Sp).  And. of course, assuming  N  goes to 

 

Sn      =       ln(N)

Sn – ln(ln(N))     =       ln(N)  –   ln(ln(N))

Sn   –   Sp        =       ln(N)  –   ln(ln(N))

Sn   –   Sp        =       ln(   N  /   ln(N)  ) 

Sn   –   Sp        =      ln(π(N))


Now we show the above with comments on the right.

Sn      =       ln(N)

 

Sn is the “vanilla” Harmonic Series

 

Sn   –   ln(ln(N))     =       ln(N)  –   ln(ln(N))

 

let’s subtract  ln(ln(N)) from each side of  =
Sn   –   Sp     =       ln(N)  –   ln(ln(N))

 

On left side, rewrite  ln(ln(N)) as its equivalent which is “Harmonic Series of Primes” (hence the subscript p).
Sn   –   Sp     =       ln(   N  /   ln(N)  ) 

 

Doing some log arithmetic, rewrite

ln(N)  –   ln(ln(N))   as its equivalent of

ln(   N  /   ln(N)  ) 

Sn   –   Sp     =      ln(π(N))

 

 

 

(   N  /   ln(N)  )    is  really the “Prime Counting Function” so if we take the ln of it  we  get

ln(π(N))  which is another way of saying that  Sn   –   S over N  is  the ln of the number of primes over N.

 

And note that Sn   –   Sp    is, to coin a phrase,

the “Harmonic Series of Composites

Sc  =  ln(π(N))

 

So that’s it.  In just a few simple steps we are able to show that the “Harmonic Series of Composites” (to coin a phrase)  is simply the log of the Prime Counting Function!   

Sc  =        ln(π(N))

 

AND we have seen  that the actual computations (thru N = 1 Billion) supports this!  But we (I) still do NOT have any intuitive feeling as to WHY!

 

AND,  try as I might,  I can NOT find any references to this “discovery” anywhere on the internet.  Oh well… time to accept it for what it is… an interesting mystery.

 

The End

 

 

No Comments on Math Mystery Wrap Up
Categories: Uncategorized

Math Mystery Followup

Numeric Precision and Order of Calculations

As They Apply To

Gerry’s Math Mystery Conjecture

Also read prior article  A Math Mystery   as well as   the next 2 articles

    Math Mystery Wrap Up

Epilogue to the Composites Chronicle

So, this will be the most engrossing blog post ever!   Hello!? … Hello!?… Is anybody out there!?

Actually,  he meant to say…

You’re gonna need a bigger computer.

This article is a historical record for myself but for some geeky computer types with an interest in math, or vice versa, you may find it of interest. This article has to do with:

1 – The differences in data types and how that affects calculations in our programs; especially programs that calculate things like a numeric series (like the harmonic series… e.g.)

2 – How the Order of calculation also makes a difference in the result. For example, in the above Harmonic Series, does it matter whether we start at the “left”

(1/1 then 1 /2 then 1/3 then… 1/n) or whether we start at the “right” and move back to the beginning of the series

(e.g. 1/n then 1/(n-1) then… 1/3 then 1/ 2 then 1/1).

The data types aspect is pretty obvious and is part of Programming 101.

In the prior article, “An Actual Math Mystery,” I used the C# program named SumOfReciprocals.exe to compute a few things over differing ranges. The purpose of the calculations was/is to help confirm, or to dispel the conjecture that:

ln(Cp) + Sp = Sn

Again, read An Actual Math Mystery

The SumOfReciprocals program mainly computes the following two series (plus a few other things). The user specifies the range of values on the screen.   Anyway, it computes the following:

“Vanilla Harmonic Series”

Harmonic Series of Primes

The following is an example test run:

 

 

The original program used C# doubles as the numeric data type (like so)

double dSumOfVanillaSeries;

double dSumOfPrimeSeries;

With doubles we get 15-16 significant digits. But could we do better?

Also, the computation of the two series was performed “left to right.” That is, smallest denominator to highest denominator… 1/1 + 1/ 2 + 1/3 …

As it turns out, the order of evaluation can make a difference. Look here

https://tomroelandts.com/articles/the-harmonic-series

So what would the difference/improvement be if we changed the order of evaluation (if any)?

After thinking about these issues for a while, I improved the SumOfReciprocals program by doing the following:

..1..   Variables were changed from double to decimal. This is a big improvement because the decimal data type provides 28-29 significant digits vs 15-16 for double.

..2..   The order of evaluation was changed to be a user choice.  Terms can now be evaluated left–>Right or Right–>Left  (user choice via a checkbox).

So… did the improvements to the program make a significant difference?   As it turns out,  for what I am investigating the improvements in “accuracy” (precision) don’t matter. What I’m after is whether it’s true that

Ln(pi(n)) + Sp = Sn

which means I use the SumOfReciprocals computations to see whether it looks like

(Sn / ( Ln(pi(n)) + Sp)) ~ 1        as n –> infinity

All that said, I can only run the SumOfReciprocals up to n = 1 Billion which takes about 35 minutes. So, to get results for 1 Trillion would require about 583 hours! I don’t think I’ll be doing that any time soon (although I’d like to).

In any event, and for what it’s worth,   the following show a comparison of a few results before and after the program improvements to SumOfReciprocals.exe.

Computing the RATIO (what I’m really interested in)

For n = 1 to 1 Billion

Before improvements using doubles and left–> right computation

RATIO = 1.01251978630066

After improvements using decimals and right–>left computation

RATIO = 1.0125194916706126049689541998

Color  shows where the differences begin. Even after improving by going from double to decimal data types and using right–>left processing, for n=1 Billion, the difference in the RATIO is negligible.

So just for grins, let’s see what differences there are with the order of processing the terms… The color coding will help us spot the differences.

n = 1.. 1 Billion

Starting Low and working to higher denominator (left → right)

Harmonic Series Sum = 21.300481502347944016685003449

Harmonic Series of Primes Sum = 3.2927653071574778714154682732

RATIO = 1.0125194916706126049689541998

Starting with higher denominator and working lower (right → left)

Harmonic Series Sum = 21.300481502347944016685100637

Harmonic Series of Primes Sum = 3.2927762759508852619827244781

RATIO = 1.0125189646875907288746445938

The above shows the computation differences for n = 1 .. 1 billion  depending on whether we process terms left to right, or,  right to left.

So there it stands. Experimentally it still looks like the conjecture is true but again, we’re only computing the two series up to n = 1 billion.

So, was this the most engrossing blog post ever!?

Hello!? … Hello!?… Is anybody out there!?

No Comments on Math Mystery Followup
Categories: Uncategorized

Eight

So this afternoon I see the headline “26 democratic senators call for resignation.”  I think to myself, “self, this came out of the blue.  Something must have happened…”  Then at 7:00 pm the news comes on and it’s…

 

Stop!  Please make it STOP!

 

8

Also see          Al Franken MRI                  and                      Six

 

No Comments on Eight
Categories: Uncategorized

SIX

 

 

11/15/2017 —————————–>  12/1

 

Damn it!

No Comments on SIX
Categories: Uncategorized

Al Franken MRI

 

Recent astounding technological developments have been made in MRI brain imaging and recording. It’s now possible to give patients specific hallucinogenic drugs and pentothal (facilitates the recall of painful repressed memories), and record what they “see and hear.” Unfortunately, it’s currently possible to only record a few seconds and sometimes only a “still image” is possible (above).  In either case the results can be astounding. That said, below is a recent recording made of Al Franken’s experience while undergoing therapy with his psychiatrist.

 

 

 

No Comments on Al Franken MRI
Categories: Uncategorized

An Actual Math Mystery

The Mystery Formula

Note —>  There’s  3 follow up articles to this one. 

Math Mystery Follow Up

Math Mystery Wrap Up

Epilogue to the Composites Chronicle

On Nov. 1 I found the following sheet of notebook paper with some formulas written on it. 

It was tucked away in a remote corner of a bookshelf.

 

Here it is transcribed with some annotation and easier to read:

 

ln(Cp) + Sp = Sn

next  convert  Cp         see  https://en.wikipedia.org/wiki/Prime-counting_function

ln( n / ln(n) ) + Sp = Sn

ln(n) – ln(ln(n)) + Sp = Sn

Sp = Sn+ ln(ln(n)) – ln(n)

ln(n) is same as Sn so make it so below

Sp = Sn + ln(ln(n)) – Sn

Sp = ln(ln(n))

 

The above was obviously written by me and it was also obvious (to me) that it concerned the relationship of the “vanilla” Harmonic Series and the Harmonic Series of Primes. As a refresher for the reader…

The “vanilla” Harmonic Series is:

The Harmonic Series of Primes is like the “vanilla” Harmonic Series except that all of the denominators of the terms are only primes:

The paper with the Mystery Formulas must have been part of an earlier project that I had abandoned about 3-4 months ago when I was not making any progress. Anyway, that project concerned trying to find a simple “proof” of the divergence of the Harmonic Series of Primes.

 

As I said, I had eventually abandoned the “simple proof” project some months ago because I was not making progress. But what is VERY STRANGE is that:

What is  written on that sheet of notebook paper above constitutes a “simple proof” I had been looking for!… Sort Of… Let me explain… It’s fascinating.

 

But first, I need to explain the nomenclature used. That is, what the “symbols” represent (it’s extremely simple but needs to be understood).

Sp is the sum of the terms of the Harmonic Series of Primes. That is, Sp  is the “value” of the series.

Sn is the sum of the terms of the “vanilla” Harmonic Series

Cp is the Count of the prime numbers in either Sp or Sn

Ln is the natural log

 

 

That said, the last formula on the sheet of notebook paper (above) is:

Sp = ln(ln(n))

The above formula expresses the “value” of the Harmonic Series of Primes.  You’ll find the above formula that expresses the value of  Sp     in many places (e.g. Wikipedia).  Anyway, as n goes to infinity we can easily see that Sp diverges!  That is,  the Harmonic Series of Primes diverges.

Sp diverges! This is what I was trying to show, in a simple manner, in the project I abandoned months ago (due to lack of progress).

 

 

So… Do the simple formulas on the Mysterious Sheet of Notebook Paper

actually represent a simple proof that I had been searching for?

Wellllllllll….. maybe.

It totally depends on whether the first formula is true. And that formula is:

Formula 1  –>       ln(Cp) + Sp = Sn

 

So is it true? Although I don’t remember doing so, I had apparently written this stuff down some months ago. If I had seen it somewhere I am pretty sure I’d remember. Now what’s really interesting is that, when I look at that first formula (just above),

I can’t think of any reason why adding the log of the count of terms with a prime denominator, to the value of the Harmonic Series of Primes, would equal the value of the vanilla Harmonic Series!!!!??

I can’t think of a reason; can you? But apparently I thought that in the past! Anyway, I’ll tell you what I can do. I can “test” the formula over billions of numbers to see if it looks like it holds water. So, while that’s not a proof, per se, it would be good evidence one way or the other. Luckily, doing such an experimental test would be easy because I had already written a SumOfReciprocals” program to help with my first attempt at finding a simple proof of the divergence of the Harmonic Series of Primes.

All that was needed was a few lines of code to display, at the end of each test, the values of each term in Formula 1 (above). For each test execution, the SumOfReciprocals program has already accumulated the values for Cp, Sp, and Sn so all that was needed was to display them in the log. Just below you can find a screen print of one such SumOfReciprocals test execution.  Click on it to see it full size.

As it turned out, the test results appear to show that the left side of the equation asymptotically approaches the right side of the equation. i.e.

ln(Cp) + Sp ~ Sn

Here is a spreadsheet showing the results of the above where the values of the denominators range from 1..109 (1 to 1 Billion).

 

 

The spreadsheet and associated chart show the results of

 

 

Sn

_____________________________

ln(Cp) + Sp

 

 

As the above ratio approaches 1, it demonstrates that the left side of the equation approaches the right side. That is, that ln(Cp) + Sp approaches Sn

So where does that leave us?

-1-  Based on some experimental evidence, it’s my conjecture that      ln(Cp) + Sp ~ Sn

-2- If the conjecture is true, then the series of formulas on the notebook paper constitutes a very simple proof of the divergence of the Harmonic Series of Primes.

 

So, all that said, how would we prove     ln(Cp) + Sp ~ Sn ?     I’ve thought about it for some time and I can’t think of any reason why ln(Cp) would play any role at all! But the experimental results appear to powerfully indicate otherwise!

It’s all a mystery and now the original project has morphed into something much more interesting…

Proving (or disproving)

ln(Cp) + Sp ~ Sn

 

 

The End

Almost the end…  here’s the first follow up article to this one.  Click here  https://itbegsthequestion.com/math-mystery-followup/

 

Note —>  There’s  3 follow up articles to this one. 

Math Mystery Follow Up

Math Mystery Wrap Up

Epilogue to the Composites Chronicle

 

 

 

 

 

 

 

 

 

No Comments on An Actual Math Mystery
Categories: Uncategorized

CPU Bound Logging

Windows Desktop Apps That Are CPU Bound…

So What’s The Problem?

This article is a bit esoteric but if you have an interest in Windows programming you may find it interesting.  That said…

Sometimes we’ll develop CPU bound programs (“apps”) that perform Bizillions of calculations. For example, a program that finds the prime factors of very large numbers (e.g. 100 digits or more) can run for a very long time. In these types of programs I’ll typically code the “Calculation function” to periodically check whether the user (me) wants to have intermediate results or other useful information “displayed.” Also, the code would additionally wait for the user to tell the Calculation function to pause, continue, or terminate after viewing the information that was displayed. All that said, here’s the problem…

The typical Windows Desktop app (WinForms or WPF) is a message-driven program. When you click on the button that says “Factor The Number” an event message is generated and is sent to the program to be read and processed. Eventually the event message works its way to its “FactorButton_Click” routine for processing. Visual Studio generates the “button click” routines in our programs but it’s up to us to add the code inside those generated functions/methods. That code that we supply will perform the calculations and may periodically display useful information in a “log” for the user to read. Examples of the kind of information displayed might be the number that’s currently being factored, how many factors have been found so far, how long it’s been working on the current number, etc.

The “log” where the app’s useful information is displayed as text would typically be a Multi-line TextBox. That is, a TextBox serves as the “log” and is the modern GUI version of “printf” (that we would have used “back in the day”).

The act of writing to the “log” (the TextBox) will generate “paint” messages which eventually make their way to the code for the TextBox that is functioning as the “log.” When the “paint” messages are processed by the TextBox code it will actually draw the text on the screen. But the problem is that the “paint” messages for the log often won’t get to the TextBox in a timely fashion as long as the calculation routine has control! Also, the user won’t be able to scroll the TextBox because mouse clicks and keypresses won’t get processed as long as the calculation routine continues to run. The messages (text) now exist in the log’s TextBox but we can’t effectively use it, or anything else on the app’s window until the “Calculation” routine finishes. The app is effectively “frozen” until the Calculation routine ends.

I have lately been writing numerous CPU Bound “calculation” programs and the above issue had been an ongoing pain in the butt. After thinking about the problem on and off for several months I finally decided to solve the problem once and for all. 

Note:  It’s occasionally been the case that when the problem is explained to another programmer they propose “just use the Yield() or Sleep() function.” However, we need to remember, Yield() and Sleep() allow other threads to get control… but the problem is that the code to process events for your own controls, like Buttons and TextBoxes, is NOT in other threads… It’s in your own thread!   And, the next thing often proposed is to use multiple threads as part of a solution;  No thanks… that’s way too complicated and error-prone.  Anywho… persistence and patience eventually led me to the following:

Here’s the basic idea as illustrated above…

The “Log” is contained in the Memory Mapped File. A utility Class named MMFlogger in a classlib is how an app would access the log. From the perspective of an app (or programmer), the file consists of just 2 very simple things:

.1. A long integer “command” that can be read or written. How the “command” (a long integer) is interpreted and used is completely up to app. For example, in the programs I write:

0 (zero) means “continue processing”

1 means “pause” and wait for a new command.

2 means “terminate” the calculations (but not the program).

.2. The second “field” in the file can be thought of as a giant string much like the Text field of a WinForms Textbox (e.g. myTextbox.Text += “\r\nAnother message for the Textbox”;).

A user app would typically use just the following 2 MMFlogger functions/methods like so:

long lCommand = myMMFlogger.ReadCommand();

and…

string something = “\r\nAppend something to the giant string in the file”;

myMMFLogger.WriteString(something);

From the User’s (programmer’s) perspective it’s about as simple as it gets. It’s essentially like writing to a WinForms TextBox!

So ItBegsTheQuestion…

How is the User actually going to view the log?

In the flowchart you will see “Process B” which is a utility app/program that monitors the log in the MemoryMappedFile. It can be set to automatically (or manually) read the data (strings) in the log and write them to a TextBox for the User to view on the screen. Of course, the User can scroll forwards and backwards, select – copy – and paste to a text file or spreadsheet, etc. And there are buttons the User can click to have “commands” sent to the “Calculation app” (Process A) to tell it to pause, continue, terminate, etc. The User can also have the data (string) cleared from the log/file (perhaps in preparation for a new round of computations by the “Calculation app”). In a nutshell:

– We eliminate the log’s TextBox from the User app and replace it with a Memory Mapped File that the app uses just like it would use a TextBox but with the added benefit that it can now easily receive “commands” from the User (person).

– The User (person) now views and interacts with the log via a TextBox in the “Utility App” (Process B). In addition, the User (person) can now send “commands” to the “Calculation app” instructing it, for example, to pause, continue, terminate the calculations, etc.

So that’s it except for a few notes:

  1. As shown in the flowchart above, Process A is the “Calculation app.” It uses the MMFlogger Class to write text to the “Log.” The “Log” is implemented via a Memory Mapped File.

  2. Process B is a general purpose utility app for viewing the “Log” that the “Calculation app” is writing to.  It can be used with any Windows desktop application.  When we code our “Calculation app” we can, if we want, have it automatically start the utility “Log” viewing app (Process B). Or it can be started manually by the User.

  3. Above I stated that the second “field” in the Memory Mapped File can be thought of as a giant string. The truth is that you can NOT write or read strings to/from a Memory Mapped File. The strings must first be converted from/to byte[] arrays as part of the process and there are some hidden “gotchas” along the way. The utility Class MMFLogger that was developed as part of this project hides all that from you and me.

  4. As it turns out, reading/writing a Memory Mapped File is VERY FAST! It’s much faster than writing to TextBoxes so you should not fret over using the MMFlogger Class in your CPU Bound app.

If you want more details or the code/projects just ask.

 

The End

No Comments on CPU Bound Logging
Categories: Uncategorized

Statistical Primes Part 2

Statistical Primes  Part 2

Of course, the 2 helpful “prerequisites” for this article are:

Twin Primes and

Statistical Primes (part 1)

 

 

In Statistical Primes (part 1) we discussed how the TwinPrimes program originally just counted Primes and Twin Primes. Then, for the “Statistical Primes” article it was enhanced to (closely?) estimate the the counts of Primes and Twins by extrapolating from statistical samples. The technique used was a simple variation of “Stratified Sampling.” The method used there was to specify

How many strata to use and

How many elements (samples) within each stratum to process.

In particular, the elements/samples in each stratum were simply the first N numbers of each stratum. It was a very simple and easily implemented method which yielded surprisingly accurate estimates of the number of Primes and Twins.

In the prior article I noted that investigating other techniques would be left to the reader. That was kind of true… after a few days I got the bug to see if the results would be any better (or worse) if the samples, from within each of the strata , were chosen randomly. And that is what this article covers.

A button was added to the TwinPrimes program giving the user a second way to estimate the count of Primes and Twins. With that button, the samples within the strata would be chosen at random using the C# Random Class.

https://msdn.microsoft.com/en-us/library/system.random(v=vs.110).aspx 

It may interest you to know that the Random class only accepts int for parameters and only returns an int for the random number chosen. Initially this presented a small problem since the TwinPrimes program deals with really BIG numbers but the limitation was overcome by limiting the size of any single stratum to 2×109 (2 Billion or less… good enough for me for now).

Sample Results

In general, I suspected that randomly sampling N numbers within each stratum would yield more accurate estimates then using the first N numbers within each stratum. This was indeed the case but the accuracy differences were minimal at the low end and became much more pronounced as we moved to larger numbers. For example:

For the range of 1 → 1 Billion

When the first N numbers in each stratum are used for the sample then

The estimated count of Primes differs from the actual count of Primes by 0.24 of 1% (by 0.00236 of the actual count).

The estimate count of Twins differs from the actual count by 1.3% (by 0.0131 of the actual count).

When the numbers in each stratum are randomly chosen for the sample then

The estimated count of Primes differs from the actual count of Primes by 0.12 of 1% (by 0.0012 of the actual count).

The estimated count of Twins differs from the actual count by 0.2% (by 0.00195 of the actual count).

For the range of 1 → 1 Trillion

When the first N numbers in each stratum are used for the sample then

The estimated count of Primes differs from the actual count of Primes by 0.07 of 1% (by 0.00068 of the actual count).

The estimated count of Twins differs from the actual count by 0.92 of 1% (by 0.0092 of the actual count).

 

When the numbers in each stratum are randomly chosen for the sample then

The estimated count of Primes differs from the actual count of Primes by 0.04 of 1% (by 0.00041 of the actual count).

The estimate count of Twins differs from the actual count by 0.07 of 1% (by 0.00073 of the actual count).

 

 

An interesting note here. In the TwinPrimes program I chose to have the Random class/object “randomly” seeded from the system clock. As such, the estimates it gives will vary with each execution. Of course, I could have seeded the class (object) with the same number every time and the results would always be the same. But that would present its own issues. Of course, I could make it an option to do it either way but…

 

When I started I didn’t know whether one method would be significantly superior to the other but it appears that both methods of sampling give (I think) very good estimates. And of course, there are many other ways of “statistically” estimating the count of primes and prime related “stuff.”

Below are 2 things you may be interested in:

  1. Screen print of latest TwinPrimes program. The “GO” button simply uses brute force to calculate the number of Primes and Twins from “Start Number” thru “How many numbers to test…” The 2 “GO WITH SAMPLING” buttons estimate the counts using the techniques talked of above.
  1. There’s a signpost ahead… it’s a copy of a spreadsheet I used to track results.

 

 

 

 

 

 

The End

No Comments on Statistical Primes Part 2
Categories: Uncategorized

Use The Force Rachel

Rachel… may the centripetal   force be with you.

 

Wait for it!…. Wait for it!…(it’s at the end).

 

The following is real short and is the essince.

 

The End

No Comments on Use The Force Rachel
Categories: Uncategorized