Tau function
Given a positive integer, count the number of its positive divisors.
- Task
Show the result for the first 100 positive integers.
- Related task
Python
Using prime factorization
<lang Python>def factorize(n):
assert(isinstance(n, int)) if n < 0: n = -n if n < 2: return k = 0 while 0 == n%2: k += 1 n //= 2 if 0 < k: yield (2,k) p = 3 while p*p <= n: k = 0 while 0 == n%p: k += 1 n //= p if 0 < k: yield (p,k) p += 2 if 1 < n: yield (n,1)
def tau(n):
assert(n != 0) ans = 1 for (p,k) in factorize(n): ans *= 1 + k return ans
if __name__ == "__main__":
print([tau(n) for n in range(1,101)])</lang>
Finding divisors efficiently
<lang Python>def tau(n):
assert(isinstance(n, int) and 0 < n) ans, i, j = 0, 1, 1 while i*i <= n: if 0 == n%i: ans += 1 j = n//i if j != i: ans += 1 i += 1 return ans
if __name__ == "__main__":
print([tau(n) for n in range(1,101)])</lang>
- Output:
[1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 8, 2, 6, 4, 4, 4, 9, 2, 4, 4, 8, 2, 8, 2, 6, 6, 4, 2, 10, 3, 6, 4, 6, 2, 8, 4, 8, 4, 4, 2, 12, 2, 4, 6, 7, 4, 8, 2, 6, 4, 8, 2, 12, 2, 4, 6, 6, 4, 8, 2, 10, 5, 4, 2, 12, 4, 4, 4, 8, 2, 12, 4, 6, 4, 4, 4, 12, 2, 6, 6, 9]
REXX
<lang rexx>/*REXX program counts the number of divisors (tau, or sigma_0) up to and including N.*/ parse arg n . /*obtain optional argument from the CL.*/ if n== | n=="," then n= 100 /*Not specified? Then use the default.*/ say 'the number of divisors (tau) for integers up to ' n " (inclusive):"; say say '─index─' center(" tau (number of divisors) ", 80, '─') w= max(7, length(n) ) /*W: used to align 1st output column. */ $= /*$: the output list, shown 20/line. */
do j=1 for n /*list # proper divisors (tau) 1 ──► N */ $= $ || right( tau(j), 4) /*add a tau number to the output list. */ if j//20\==0 then iterate /*Not a multiple of 20? Don't display.*/ say center(j-19, 7) $; $= /*display partial list to the terminal.*/ end /*j*/
if $\== then say center(j-1, 7) $ /*any residuals left to display ? */ exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ tau: procedure; parse arg x 1 y /*X and $ are both set from the arg.*/
if x<6 then return 2 + (x==4) - (x==1) /*some low #s should be handled special*/ odd= x // 2 /*check if X is odd (remainder of 1).*/ if odd then do; #= 2; end /*Odd? Assume divisor count of 2. */ else do; #= 4; y= x % 2; end /*Even? " " " " 4. */ /* [↑] start with known number of divs*/ do j=3 for x%2-3 by 1+odd while j<y /*for odd number, skip even numbers. */ if x//j==0 then do /*if no remainder, then found a divisor*/ #= # + 2; y= x % j /*bump # of divisors; calculate limit.*/ if j>=y then do; #= # - 1; leave; end /*reached limit?*/ end /* ___ */ else if j*j>x then leave /*only divide up to √ x */ end /*j*/ /* [↑] this form of DO loop is faster.*/</lang>
- output when using the default input:
the number of divisors (tau) for integers up to 100 (inclusive): ─index─ ─────────────────────────── tau (number of divisors) ─────────────────────────── 1 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 2 6 2 6 21 4 4 2 8 3 4 4 6 2 8 2 6 4 4 4 9 2 4 4 8 41 2 8 2 6 6 4 2 10 3 6 4 6 2 8 4 8 4 4 2 12 61 2 4 6 7 4 8 2 6 4 8 2 12 2 4 6 6 4 8 2 10 81 5 4 2 12 4 4 4 8 2 12 4 6 4 4 4 12 2 6 6 9