August 17, 2024

This article is about a fun computing project, not math. The mathmatical aspects of this concept and how it connects to other (very important) topics is beyond the scope of this article and my understanding. I will link some resources, including OEIS formatted like this: A002819. This topic is very interesting so I encourage you to research this yourself.

The Liouville function (commonly expressed as λ(n); see A008836) is defined for a given natural number, *n*, as -1 raised to the power of the number of prime divisors *n* has, counted with multiplicity (Ω(n); see A001222).

For input *n*, the Liouville function will output -1 for any number with an odd big omega like primes and perfect cubes (except 1); it will output 1 for numbers with an even big omega like semiprimes and perfect squares. These examples are in no way exhaustive, the function is defined for all natural numbers.

Mathematicians have found it useful to study the partial sums of the Liouville function or its variants because it is connected the the distribution of primes thus have important consequences. Sums of λ(n)/n is studied but this page will focus on the partial sum of just the function (A002819): the sum of all Liouville function values for all natural numbers up to a value; I will refer to this as the summatory Liouville funciton, or L(n) for short.

George PĆ³lya showed that if most natural numbers have an odd number of prime factors (if L(n) is always negative), the Riemann hypothesis would be implied. This was proven false by C. Brian Haselgrove in 1958 and a counterexample via L(n) was found later. The smallest counterexample is L(906150257) = 1.

The counterexample is pretty large which is what made me interested in it. This just seems like a pretty interesting program in general. I have written a program to calculate values of L(n).

In December 2021, as one of my first projects in C, I wrote a program that naively calculates L(n). See it here (commit 1532234). The program was slow because it repeated a lot of computations.

I will gloss over details here. Details can be found in the code and readme file.

λ is completely multiplicative so the programs keeps a big table of already computed values to speed everything up. The size of the table can be adjusted at compile-time but it's typically about 10-500 billion values. Note that each value only uses one bit.

The program spends a lot time doing trial division if a number doesn't have a small divisor, so I have implemented a prime number table, generated at start up using Sieve of Eratosthenes, that contains all 203280221 primes less than 2^{32}. For values larger than that, I used a hashed Miller-Rabin test documented here. The program frequently checks if a number is primes.

The program also keeps 30030 value long table of GCD(1, n) for n less than 30030. Note that 30030 is a primorial (see A002110). This is used for an initial division.

I used the unix *pthreads* library. Both the main computation and the generation of the primes table is multithreaded. The program computes values in blocks to be processed by a single main thread.

A barebones version of the program can sum and store each lambda value to 1 billion in about 30 second on my Intel Core Ultra & 155H running WSL.

Note that if you just want L(n) at a specific value, you can skip a lot of values due to how the function behaves, my goal is to evaluate all values up to a certain number and isolate interesting results.

The program outputs a line if the following event happens. All this will be available in the sections below.

- L(n) is zero. See A028488
- L(n) hits a new maximum or minimum record. See A051470 and A002053 respectively.
- λ is the same value for a record length. Equivalently, L(n) is monotonic over the integers for a record interval. See A175201 and A175202.
- Periodic output for graphs, analysis, and checkpointing.

Also see this section of the readme.

All these events are outputted to a log file, the data will be presented below.

I used to the free sign up credits on Google Cloud Platform and Oracle Cloud Infrastructure to run my programs. On free accounts, Google only let me run 8 vCPUs and Oracle only let me run 24, so the computation took a while. I will refer to the OCI VM as my primary computer and the GCP one as my secondary. Paying for them would've been too expensive for my level of interest in this project. Anyways, if you or your insitution have a supercomputer cluster I can borrow, let me know.

I ran my programs on both computers with a 192 billion value long table which took 24 GB. There is also the 4 billion bit prime table which is 500 MB. The programs used about 25 GB of memory.

Due to the nature of the function, one slient hardware error can cascade into the results. The servers running the program probably has ECC but I have implemented no integrity checks. Running the program on two independent machines mitigates most of my concern but there is still a chance that big cosmic rays is out to get me.

The most impactful error would be in low values of the primes table.

The studies on memory error rates states values all over the place, so I can't do fun estimations and weird comparisons comparing memory bit half life to uranium or something.

Values up to 604.7 billion was run on both primary and secondary computers with matching results.

Primary computation took about 980938 seconds (11.4 days) where it summed 15589 blocks of 2^{26} values, in total about 1.046 trillion values. For the cumulative average speed of about 1.066 million values per second.

Above shows the increasing time it takes for each block to evalulated, accurate to the second. Note that the jumps happen at multiples of the tail table (192 billion).

**Note that THESE RESULTS ARE NOT GURANTEED TO BE CORRECT. The chances are low, but there may be invisible bugs or hardware errors that tampered with the results.** Again, values up to 604.7 billion are ran twice with matching results. Additionally, outputs up to a trillion has been check against the OEIS (A090410)

File: Values up to 32768, every value

File: Values up to 1046000000000, sampled every 100000000

Value of the first trillion. One point every 10^{8}

Value of the first 100 billion. One point every 10^{8}

See also: A028488

The 252 zeros for values up to a trillion is as follows: 2, 4, 6, 10, 16, 26, 40, 96, 586, 906150256, 906150294, 906150308, 906150310, 906150314, 906151516, 906151576, 906152172, 906154582, 906154586, 906154590, 906154594, 906154604, 906154606, 906154608, 906154758, 906154760, 906154762, 906154764, 906154766, 906154768, 906154770, 906154786, 906154788, 906154790, 906154792, 906154794, 906154798, 906154824, 906154826, 906154828, 906154830, 906154836, 906154838, 906154856, 906154858, 906154864, 906154882, 906154884, 906154886, 906154888, 906154890, 906154892, 906154894, 906154908, 906154912, 906154914, 906154928, 906154930, 906154934, 906154936, 906154946, 906154950, 906154954, 906180358, 906180362, 906180364, 906180366, 906180370, 906180374, 906180376, 906180386, 906180388, 906180390, 906180518, 906180520, 906180524, 906180534, 906180536, 906180554, 906192698, 906192700, 906192702, 906192846, 906192866, 906192904, 906192906, 906192966, 906192970, 906192972, 906192976, 906192978, 906192984, 906193228, 906193234, 906193244, 906193246, 906193248, 906193302, 906193304, 906193308, 906193310, 906193336, 906193338, 906193344, 906193418, 906193420, 906193440, 906193464, 906193466, 906193472, 906193474, 906193476, 906193478, 906194914, 906194920, 906194922, 906194924, 906194930, 906194932, 906194946, 906194948, 906194950, 906194968, 906194978, 906194980, 906195096, 906195098, 906195100, 906195104, 906195106, 906195108, 906195150, 906195152, 906195296, 906195298, 906195986, 906195988, 906195990, 906196008, 906196010, 906196014, 906196016, 906196040, 906196042, 906196044, 906196052, 906196056, 906196072, 906196074, 906196076, 906196080, 906196082, 906196092, 906196098, 906208712, 906208714, 906208730, 906208732, 906208734, 906209040, 906209064, 906209066, 906209068, 906209070, 906209224, 906209226, 906209228, 906209230, 906209232, 906209236, 906209238, 906209240, 906209242, 906209272, 906209282, 906209284, 906477702, 906477714, 906477734, 906477812, 906477818, 906477866, 906477868, 906477870, 906477900, 906477902, 906477906, 906477928, 906477932, 906477934, 906477936, 906486640, 906486804, 906486806, 906486808, 906486810, 906486812, 906486816, 906486818, 906486820, 906486832, 906486842, 906486854, 906486856, 906486908, 906486914, 906486916, 906486974, 906487002, 906487004, 906487064, 906487066, 906487068, 906487070, 906487072, 906487078, 906487084, 906487086, 906487102, 906487104, 906487180, 906487184, 906487186, 906487190, 906487192, 906487194, 906487204, 906487206, 906487258, 906487260, 906487262, 906487264, 906487270, 906487288, 906487932, 906487934, 906487936, 906487938, 906487948, 906487974, 906487994, 906488002, 906488004, 906488006, 906488008, 906488010, 906488022, 906488026, 906488066, 906488068, 906488076, 906488080

The next block of zeros is at around 351 trillion.

File: Minimums up to a trillion (25MB)

File: Maximums up to a trillion

Within the first 1.046 trillion, the minimum value is -1038386 at 835018639060. The maximum is 829 at 906316571.

I will link files with the position and values of all minimums and maximums below.

0 is 1 or even big omega, and 1 is -1 or odd big omega.

of | length | position | ln(position) |
---|---|---|---|

0 | 1 | 1 | 0.00 |

1 | 1 | 2 | 0.69 |

1 | 2 | 2 | 0.69 |

0 | 2 | 9 | 2.20 |

1 | 3 | 11 | 2.40 |

0 | 3 | 14 | 2.64 |

1 | 4 | 17 | 2.83 |

1 | 5 | 27 | 3.30 |

1 | 6 | 27 | 3.30 |

0 | 4 | 33 | 3.50 |

0 | 5 | 54 | 3.99 |

0 | 6 | 140 | 4.94 |

0 | 7 | 140 | 4.94 |

1 | 7 | 170 | 5.14 |

0 | 8 | 213 | 5.36 |

0 | 9 | 213 | 5.36 |

1 | 8 | 279 | 5.63 |

1 | 9 | 428 | 6.06 |

0 | 10 | 1934 | 7.57 |

0 | 11 | 1934 | 7.57 |

0 | 12 | 1934 | 7.57 |

1 | 10 | 5879 | 8.68 |

1 | 11 | 5879 | 8.68 |

1 | 12 | 13871 | 9.54 |

1 | 13 | 13871 | 9.54 |

1 | 14 | 13871 | 9.54 |

0 | 13 | 35811 | 10.49 |

0 | 14 | 38405 | 10.56 |

0 | 15 | 38405 | 10.56 |

1 | 15 | 41233 | 10.63 |

1 | 16 | 171707 | 12.05 |

0 | 16 | 200938 | 12.21 |

0 | 17 | 200938 | 12.21 |

0 | 18 | 389409 | 12.87 |

1 | 17 | 1004646 | 13.82 |

1 | 18 | 1004646 | 13.82 |

1 | 19 | 1633357 | 14.31 |

0 | 19 | 1792209 | 14.40 |

1 | 20 | 5460156 | 15.51 |

0 | 20 | 5606457 | 15.54 |

0 | 21 | 8405437 | 15.94 |

0 | 22 | 8405437 | 15.94 |

0 | 23 | 8405437 | 15.94 |

0 | 24 | 8405437 | 15.94 |

1 | 21 | 11902755 | 16.29 |

1 | 22 | 21627159 | 16.89 |

1 | 23 | 21627159 | 16.89 |

1 | 24 | 38821328 | 17.47 |

1 | 25 | 41983357 | 17.55 |

0 | 25 | 68780189 | 18.05 |

0 | 26 | 68780189 | 18.05 |

0 | 27 | 68780189 | 18.05 |

0 | 28 | 68780189 | 18.05 |

1 | 26 | 179376463 | 19.00 |

1 | 27 | 179376463 | 19.00 |

1 | 28 | 179376463 | 19.00 |

1 | 29 | 179376463 | 19.00 |

1 | 30 | 179376463 | 19.00 |

1 | 31 | 179376463 | 19.00 |

1 | 32 | 179376463 | 19.00 |

1 | 33 | 179376463 | 19.00 |

0 | 29 | 880346227 | 20.60 |

0 | 30 | 880346227 | 20.60 |

0 | 31 | 880346227 | 20.60 |

0 | 32 | 880346227 | 20.60 |

0 | 33 | 880346227 | 20.60 |

0 | 34 | 85910903650 | 25.18 |

0 | 35 | 87635944146 | 25.20 |

1 | 34 | 130292951546 | 25.59 |

1 | 35 | 130292951546 | 25.59 |

1 | 36 | 130292951546 | 25.59 |

0 | 36 | 284340107954 | 26.37 |

0 | 37 | 284340107954 | 26.37 |

1 | 37 | 393142151459 | 26.70 |

1 | 38 | 393142151459 | 26.70 |

The position of longer repeats is roughly exponential

hsing@hsing:/mnt/c/Users/hsing/Desktop/website/main-website/liouville-lambda/resource$ du -h *.txt 384K every.txt 16K maxrelease.txt 25M minrelease.txt 23M output-gcp.txt 26M output-oci.txt 308K periodicrelease.txt hsing@hsing:/mnt/c/Users/hsing/Desktop/website/main-website/liouville-lambda/resource$ md5sum *.txt 96004810c1066d4ca460ddfc2d157a6b every.txt c0e9397c14d50a14d36f7ba994a36f19 maxrelease.txt e813f20e77044eb7d76d7ad177af66c4 minrelease.txt 193e86d545cfc8b161361d4cecce34ff output-gcp.txt f3cac0fb02febcd059906c4267d53ab8 output-oci.txt 76a401816220993958e22aec3253a6f5 periodicrelease.txt hsing@hsing:/mnt/c/Users/hsing/Desktop/website/main-website/liouville-lambda/resource$ sha1sum *.txt 827f6d63555f66092767764eac1b126cae6e87d7 every.txt e5ea2da8c2c039d101dab0a49a43c8f6f1ff0c59 maxrelease.txt 758d54e0b47c478d4754bce47d7b534d3141d062 minrelease.txt 9a8b5ec8df6b6ef70c6f279c78eb5cbf572587d8 output-gcp.txt 85621ba52fdf40f7b46a6a445d6d0668d4d6f73b output-oci.txt d173364ca47a81e9b61106b33d27c58623dc1be9 periodicrelease.txt hsing@hsing:/mnt/c/Users/hsing/Desktop/website/main-website/liouville-lambda/resource$

Lehman, R. S. (1960). On Liouville's function. Mathematics of Computation, 311-320.

Contact me at my email listed below.