Computer proof that completely multiplicative sequences have discrepancy greater than 2
Revision as of 15:09, 1 February 2010 by Teorth
- a reduced expression for f(n) for each n, of the form f(n) = +f(m) or f(n)=-f(m). Thus for instance if we know that f(2)=-1, then we can reduce f(12)=-f(3). This is recorded by an array vals, thus for instance vals=-3 would be recording the fact that f(12)=-f(3).
- Upper and lower bounds for each of the partial sums f[1,n] := f(1)+...+f(n).
The "easy" deductions that the algorithm makes automatically are:
- consequences of multiplicativity (e.g. f(n^2)=1);
- Adjusting upper and lower bounds for f[1,n] based on knowledge of f[1,n-1] and f(n), or of f[1,n+1] and f(n+1);
- Deducing the value of f(n) given enough information about f[1,n] and f[1,n-1]
After running the initialisation routine init(), there are three main routines:
- set(p,s): this forces f(p)=s
- deduce(): run all the easy deductions available from the current state of knowledge; halt if an error occurs and display the current state
- display(): display the current state.