(49g 50g) Divisibility Programs

[John Keith]

Here are several short programs for number theory functions related to prime factors and divisibility. I am posting them as a directory object for convenience and because of some dependencies. Some short descriptions follow, in order of the listings.

JorJ2 is the Jordan J2 function.

DDKPSI is the Dedekind Psi function.

LVL\Gl is the Liouville lambda function.

The three programs above return the value of the function for an integer n. The next three programs, A7434, A1615 and A8836 return lists of the above functions from 1 to n. They are substantially faster than using the programs above inside a loop.

\Gw (omega) is the "little" omega function.

\GW (Omega) is the "big" omega function.

The last two programs, DIRCNV and DIRINV, are the last program in post #1, and the program in post #2 respectively in this thread. They are listed here because they are called by the list-based programs above.


Various programs require Factor 1.1, ListExt and MOB, Gerald H's SystemRPL program for the Moebius mu function.

Code:


DIR
  JorJ2
  \<< DIVIS DUP EULER DUP REVLIST ROT REVLIST * * 0 + \GSLIST
  \>>
  DDKPSI
  \<< DIVIS DUP REVLIST MOB SQ * 0 + \GSLIST
  \>>
  LVL\Gl
  \<< 1 OVER I\->R 1. > { SWAP IFACTOR SIZE 2. MOD { NEG } IFT } { NIP } IFTE
  \>>
  A7434
  \<< LSEQ DUP MOB DIRCNV
  \>>
  A1615
  \<< LSEQ DUP MOB ABS DIRCNV
  \>>
  A8836
  \<< LSEQ MOB ABS DIRINV
  \>>
  \Gw
  \<< DUP I\->R 1. > { IFACTOR LGRP SIZE R\->I } { DROP 0 } IFTE
  \>>
  \GW
  \<< DUP I\->R 1. > { IFACTOR SIZE R\->I } { DROP 0 } IFTE
  \>>
  DIRCNV
  \<< DUP SIZE R\->I \-> n
  \<< 1 n
    FOR k DUP2 k DIVIS SWAP OVER LPICK UNROT LPICK REV * LSUM UNROT
    NEXT DROP2 n \->LIST
  \>>
  \>>
  DIRINV
  \<< DUP SIZE R\->I \-> b n
  \<< { 1 } 2 n
    FOR k k DIVIS b OVER TAIL LPICK UNROT OVER SWAP REV TAIL LPICK ROT * LSUM NEG +
    NEXT
  \>>
  \>>
END