(49g 50g) Ramanujan Tau Function

[John Keith]

These programs compute the Ramanujan tau function (A000594) for positive integers. All three programs use Gerald Hilliers SUMDIVISORS command from hpcalc.org, and must be run in exact mode. The last two programs also require the ListExt Library. Neither program is very fast, and use of an emulator is recommended for large integers.

Edited 10/13/2018 to replace the first two programs with slightly smaller and faster versions.

The first program is the most general, and can calculate tau(n) for any size integer, given enough time. This is essentially the same algorithm as program #2 here.

Code:


\<<
  IF DUP 1 >
  THEN DUPDUP * \-> n n2
    \<< 0 1 n 1 -
      FOR k k DUPDUP 35 * 52 n * - OVER * 18 n2 * + * * n k DUP 1 SUMDIVISORS UNROT - 1 SUMDIVISORS * * +
      NEXT 24 * n DUP 1 SUMDIVISORS SWAP 4 ^ * SWAP -
    \>>
  END
\>>

The next program is about 25% faster than the previous one. It is limited to integers less than 2000 or so because of the memory required by the precomputed sigma values.

Code:


\<<
  IF DUP 1 >
  THEN DUPDUP * \-> n n2
    \<< n 1 - DUP LSEQ 1 SUMDIVISORS DUP REV * 1 ROT
      FOR k k DUPDUP 35 * 52 n * - OVER * 18 n2 * + * *
      NEXT n 1 - \->LIST * LSUM 24 * n DUP 1 SUMDIVISORS SWAP 4 ^ * SWAP -
    \>>
  END
\>>

The last program returns a list of tau values from 1 through n. It is significantly faster than computing the individual values with the programs above, but still quite slow for large integers.

Code:


\<< DUP 1 - DUP LSEQ 1 SUMDIVISORS \-> n n1 s
  \<< 1 1 n1
    FOR k k DUPN k \->LIST REV s 1 k SUB * LSUM -24 * k /
    NEXT n \->LIST
  \>>
\>>

EDIT: The program above can be used to compute many other sequences if the -24 in line 3 is replaced by another number. Details and a more general program here.