Information and Pre-computed Results to my Summatory Liouville Function Program

What is this?
Source code
Time complexity analysis
Miscellaneous graphs
Actual research

As of 2021-11-22, i'm semi-actively working on this project, the page will be frequently updated.

What is this?

This is a program that evaluates the summatory Liouville function up to an amount and outputs the sum along the way. The summatory Liouville function is a function that, given a natural number, for every natural number less than it: adds 1 to the sum if the number has an even number of prime factors and subtracts one if the number has an odd number of prime factors.

This function is known for its connection with the polya conjecture: where George Polya conjected that most numbers has an odd number of prime factors (sum Liouville function of negative.) This conjecture was disproved by C. Brian Haselgrove and a counterexample was found later at about 906 million by Minoru Tanaka.

Other generalizations and connections to other areas of mathmatics can be made from this function

Source code

The source code is hosted on this github repo. You can improve it if you want to.


Below are the results for a run I'm doing. The table/list lists an entry every interval of 10,000,000 or when the function sums to 0.

NOTE: I CANNOT GUARANTEE THE ACCURACY OF THE RESULTS, it's most likely correct but there may be hardware instability or bugs, which would cascade due to the nature of the program. The result is certainly correct up to n ≤ 906,488,079 after cross referencing other sources. An identical calculation that is a few billion behind is being made and I will make sure the results from both runs match

Results as a text file. Format: {Timestamp} - {n}: {L(n)}. Updated ~daily.
This file contains duplicate entries created when the program is updated or restarted. Entries with two slashes in it (comment) should be ignored, those are sometimes accompanied with its reason of existance. See above paragraph regardingthe integrity of the data

It should take less than 20 minutes to compute the value of any number in range given the listed results

Results visualized:

results visualized
The value of of the summatory Liouville function from 1e7 to 1.9e9. Sampled every 1e7
results visualized 2
The value of of the summatory Liouville function from 1e7 to 3.77e9. Sampled every 1e7

more graphs will be coming as more values are computed

Time complexity analysis

This analysis is made before the code was greatly optimized. Although I am pretty sure the below stated result still apply since the optimization only improved the coefficent

Using logs generated by an overnight run I made. A complexity a little better than O(n sqrt n) can be estimated. Below are two graphs that demostrate it:

graph 1
Time taken to compute and sum 10 million values, and sqrt(x) fitted to it.
Y-axis in seconds. X-axis is from 0 to 1.17 billion
graph 2
Total time taken to compute up to 1.17 billion fitted to n sqrt n. Y-axis in seconds

Miscellaneous graphs

time before and after optimization
Time taken to evaluate 1e7 values before and after the 6k±1 and data types optimization

Actual research

This project is mainly made for fun and for me to learn the C language. I'm aware that a lot of improvements can be made: anything from multithreading to distributed computing, so if anyone has an idea or have the ability to do something, let me know at [email protected]

If you want to see some actual research about this topic and an implimentation made on a supercomputer, check out

Borwein, Peter, Ron Ferguson, and Michael Mossinghoff. "Sign changes in sums of the Liouville function." Mathematics of computation 77.263 (2008): 1681-1694.