Tau function: Difference between revisions
Not a robot (talk | contribs) (Add COBOL) |
Not a robot (talk | contribs) (Add Modula-2) |
||
Line 1,034: | Line 1,034: | ||
{{out}} |
{{out}} |
||
<pre>{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}</pre> |
<pre>{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}</pre> |
||
=={{header|Modula-2}}== |
|||
{{trans|C}} |
|||
<lang modula2>MODULE TauFunc; |
|||
FROM InOut IMPORT WriteCard, WriteLn; |
|||
VAR i: CARDINAL; |
|||
PROCEDURE tau(n: CARDINAL): CARDINAL; |
|||
VAR total, count, p: CARDINAL; |
|||
BEGIN |
|||
total := 1; |
|||
WHILE n MOD 2 = 0 DO |
|||
n := n DIV 2; |
|||
total := total + 1 |
|||
END; |
|||
p := 3; |
|||
WHILE p*p <= n DO |
|||
count := 1; |
|||
WHILE n MOD p = 0 DO |
|||
n := n DIV p; |
|||
count := count + 1 |
|||
END; |
|||
total := total * count; |
|||
p := p + 2 |
|||
END; |
|||
IF n>1 THEN total := total * 2 END; |
|||
RETURN total; |
|||
END tau; |
|||
BEGIN |
|||
FOR i := 1 TO 100 DO |
|||
WriteCard(tau(i), 3); |
|||
IF i MOD 20 = 0 THEN WriteLn END |
|||
END |
|||
END TauFunc.</lang> |
|||
{{out}} |
|||
<pre> 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</pre> |
|||
=={{header|Nim}}== |
=={{header|Nim}}== |
Revision as of 02:12, 9 January 2022
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Given a positive integer, count the number of its positive divisors.
- Task
Show the result for the first 100 positive integers.
- Related task
11l
<lang 11l>F tau(n)
V ans = 0 V i = 1 V j = 1 L i * i <= n I 0 == n % i ans++ j = n I/ i I j != i ans++ i++ R ans
print((1..100).map(n -> tau(n)))</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]
Action!
<lang Action!>CARD FUNC DivisorCount(CARD n)
CARD result,p,count result=1 WHILE (n&1)=0 DO result==+1 n=n RSH 1 OD
p=3 WHILE p*p<=n DO count=1 WHILE n MOD p=0 DO count==+1 n==/p OD result==*count p==+2 OD
IF n>1 THEN result==*2 FI
RETURN (result)
PROC Main()
CARD max=[100],n,divCount
PrintF("Tau function for the first %U numbers%E",max) FOR n=1 TO max DO divCount=DivisorCount(n) PrintC(divCount) Put(32) OD
RETURN</lang>
- Output:
Screenshot from Atari 8-bit computer
Tau function for the first 100 numbers 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
ALGOL W
<lang algolw>begin % find the count of the divisors of the first 100 positive integers %
% calculates the number of divisors of v % integer procedure divisor_count( integer value v ) ; begin integer total, n, p; total := 1; n := v; % Deal with powers of 2 first % while not odd( n ) do begin total := total + 1; n := n div 2 end while_not_odd_n ; % Odd prime factors up to the square root % p := 3; while ( p * p ) <= n do begin integer count; count := 1; while n rem p = 0 do begin count := count + 1; n := n div p end while_n_rem_p_eq_0 ; p := p + 2; total := total * count end while_p_x_p_le_n ; % If n > 1 then it's prime % if n > 1 then total := total * 2; total end divisor_count ; begin integer limit; limit := 100; write( i_w := 1, s_w := 0, "Count of divisors for the first ", limit, " positive integers:" ); for n := 1 until limit do begin if n rem 20 = 1 then write(); writeon( i_w := 3, s_w := 1, divisor_count( n ) ) end for_n end
end.</lang>
- Output:
Count of divisors for the first 100 positive integers: 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
AppleScript
<lang applescript>on factorCount(n)
if (n < 1) then return 0 set counter to 2 set sqrt to n ^ 0.5 if (sqrt mod 1 = 0) then set counter to 1 repeat with i from (sqrt div 1) to 2 by -1 if (n mod i = 0) then set counter to counter + 2 end repeat return counter
end factorCount
-- Task code: local output, n, astid set output to {"Positive divisor counts for integers 1 to 100:"} repeat with n from 1 to 100
if (n mod 20 = 1) then set end of output to linefeed set end of output to text -3 thru -1 of (" " & factorCount(n))
end repeat set astid to AppleScript's text item delimiters set AppleScript's text item delimiters to "" set output to output as text set AppleScript's text item delimiters to astid return output</lang>
- Output:
<lang applescript>"Positive divisor counts for integers 1 to 100:
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"</lang>
Arturo
<lang rebol>tau: function [x] -> size factors x
loop split.every:20 1..100 => [
print map & => [pad to :string tau & 3]
]</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
AWK
<lang AWK>
- syntax: GAWK -f TAU_FUNCTION.AWK
BEGIN {
print("The tau functions for the first 100 positive integers:") for (i=1; i<=100; i++) { printf("%2d ",count_divisors(i)) if (i % 10 == 0) { printf("\n") } } exit(0)
} function count_divisors(n, count,i) {
for (i=1; i*i<=n; i++) { if (n % i == 0) { count += (i == n / i) ? 1 : 2 } } return(count)
} </lang>
- Output:
The tau functions for the first 100 positive integers: 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
BASIC
<lang gwbasic>10 DEFINT A-Z 20 FOR I=1 TO 100 30 N=I: GOSUB 100 40 PRINT USING " ##";T; 50 IF I MOD 20=0 THEN PRINT 60 NEXT 70 END 100 T=1 110 IF (N AND 1)=0 THEN N=N\2: T=T+1: GOTO 110 120 P=3 130 GOTO 180 140 C=1 150 IF N MOD P=0 THEN N=N\P: C=C+1: GOTO 150 160 T=T*C 170 P=P+2 180 IF P*P<=N GOTO 140 190 IF N>1 THEN T=T*2 200 RETURN</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
BCPL
<lang bcpl>get "libhdr"
let tau(n) = valof $( let total = 1 and p = 3
while (n & 1) = 0 $( total := total + 1 n := n >> 1 $) while p*p <= n $( let count = 1 while n rem p = 0 $( count := count + 1 n := n / p $) total := total * count p := p + 2 $) if n>1 then total := total * 2 resultis total
$)
let start() be
for n=1 to 100 $( writed(tau(n), 3) if n rem 20 = 0 then wrch('*N') $)</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
C
<lang c>#include <stdio.h>
// See https://en.wikipedia.org/wiki/Divisor_function unsigned int divisor_count(unsigned int n) {
unsigned int total = 1; // Deal with powers of 2 first for (; (n & 1) == 0; n >>= 1) { ++total; } // Odd prime factors up to the square root for (unsigned int p = 3; p * p <= n; p += 2) { unsigned int count = 1; for (; n % p == 0; n /= p) { ++count; } total *= count; } // If n > 1 then it's prime if (n > 1) { total *= 2; } return total;
}
int main() {
const unsigned int limit = 100; unsigned int n;
printf("Count of divisors for the first %d positive integers:\n", limit); for (n = 1; n <= limit; ++n) { printf("%3d", divisor_count(n)); if (n % 20 == 0) { printf("\n"); } }
return 0;
}</lang>
- Output:
Count of divisors for the first 100 positive integers: 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
C++
<lang cpp>#include <iomanip>
- include <iostream>
// See https://en.wikipedia.org/wiki/Divisor_function unsigned int divisor_count(unsigned int n) {
unsigned int total = 1; // Deal with powers of 2 first for (; (n & 1) == 0; n >>= 1) ++total; // Odd prime factors up to the square root for (unsigned int p = 3; p * p <= n; p += 2) { unsigned int count = 1; for (; n % p == 0; n /= p) ++count; total *= count; } // If n > 1 then it's prime if (n > 1) total *= 2; return total;
}
int main() {
const unsigned int limit = 100; std::cout << "Count of divisors for the first " << limit << " positive integers:\n"; for (unsigned int n = 1; n <= limit; ++n) { std::cout << std::setw(3) << divisor_count(n); if (n % 20 == 0) std::cout << '\n'; }
}</lang>
- Output:
Count of divisors for the first 100 positive integers: 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
CLU
<lang clu>tau = proc (n: int) returns (int)
total: int := 1 while n//2 = 0 do total := total + 1 n := n/2 end p: int := 3 while p*p <= n do count: int := 1 while n//p = 0 do count := count + 1 n := n/p end total := total * count p := p+2 end if n>1 then total := total * 2 end return(total)
end tau
start_up = proc ()
po: stream := stream$primary_output() for n: int in int$from_to(1, 100) do stream$putright(po, int$unparse(tau(n)), 3) if n//20=0 then stream$putl(po, "") end end
end start_up</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
COBOL
<lang cobol> IDENTIFICATION DIVISION.
PROGRAM-ID. TAU-FUNCTION.
DATA DIVISION. WORKING-STORAGE SECTION. 01 TAU-VARS. 03 TOTAL PIC 999. 03 N PIC 999. 03 FILLER REDEFINES N. 05 FILLER PIC 99. 05 FILLER PIC 9. 88 N-EVEN VALUES 0, 2, 4, 6, 8. 03 P PIC 999. 03 P-SQUARED PIC 999. 03 N-DIV-P PIC 999V999. 03 FILLER REDEFINES N-DIV-P. 05 NEXT-N PIC 999. 05 FILLER PIC 999. 88 DIVISIBLE VALUE ZERO. 03 F-COUNT PIC 999. 01 CONTROL-VARS. 03 I PIC 999. 01 OUT-VARS. 03 OUT-ITM PIC ZZ9. 03 OUT-STR PIC X(80) VALUE SPACES. 03 OUT-PTR PIC 99 VALUE 1.
PROCEDURE DIVISION. BEGIN. PERFORM SHOW-TAU VARYING I FROM 1 BY 1 UNTIL I IS GREATER THAN 100. STOP RUN. SHOW-TAU. MOVE I TO N. PERFORM TAU. MOVE TOTAL TO OUT-ITM. STRING OUT-ITM DELIMITED BY SIZE INTO OUT-STR WITH POINTER OUT-PTR. IF OUT-PTR IS EQUAL TO 61, DISPLAY OUT-STR, MOVE 1 TO OUT-PTR.
TAU. MOVE 1 TO TOTAL. PERFORM POWER-OF-2 UNTIL NOT N-EVEN. MOVE ZERO TO P-SQUARED. PERFORM ODD-FACTOR THRU ODD-FACTOR-LOOP VARYING P FROM 3 BY 2 UNTIL P-SQUARED IS GREATER THAN N. IF N IS GREATER THAN 1, MULTIPLY 2 BY TOTAL. POWER-OF-2. ADD 1 TO TOTAL. DIVIDE 2 INTO N. ODD-FACTOR. MULTIPLY P BY P GIVING P-SQUARED. MOVE 1 TO F-COUNT. ODD-FACTOR-LOOP. DIVIDE N BY P GIVING N-DIV-P. IF DIVISIBLE, MOVE NEXT-N TO N, ADD 1 TO F-COUNT, GO TO ODD-FACTOR-LOOP. MULTIPLY F-COUNT BY TOTAL.</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
Cowgol
<lang cowgol>include "cowgol.coh";
typedef N is uint8; sub tau(n: N): (total: N) is
total := 1; while n & 1 == 0 loop total := total + 1; n := n >> 1; end loop; var p: N := 3; while p*p <= n loop var count: N := 1; while n%p == 0 loop count := count + 1; n := n / p; end loop; total := total * count; p := p + 2; end loop; if n>1 then total := total << 1; end if;
end sub;
sub print2(n: uint8) is
print_char(' '); if n<10 then print_char(' '); else print_i8(n/10); end if; print_i8(n%10);
end sub;
var n: N := 1; while n <= 100 loop
print2(tau(n)); if n % 20 == 0 then print_nl(); end if; n := n + 1;
end loop;</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
D
<lang d>import std.stdio;
// See https://en.wikipedia.org/wiki/Divisor_function uint divisor_count(uint n) {
uint total = 1; // Deal with powers of 2 first for (; (n & 1) == 0; n >>= 1) { ++total; } // Odd prime factors up to the square root for (uint p = 3; p * p <= n; p += 2) { uint count = 1; for (; n % p == 0; n /= p) { ++count; } total *= count; } // If n > 1 then it's prime if (n > 1) { total *= 2; } return total;
}
void main() {
immutable limit = 100; writeln("Count of divisors for the first ", limit, " positive integers:"); for (uint n = 1; n <= limit; ++n) { writef("%3d", divisor_count(n)); if (n % 20 == 0) { writeln; } }
}</lang>
- Output:
Count of divisors for the first 100 positive integers: 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
Delphi
<lang Delphi> program Tau_function;
{$APPTYPE CONSOLE}
uses
System.SysUtils;
function CountDivisors(n: Integer): Integer; begin
Result := 0; var i := 1; var k := 2; if (n mod 2) = 0 then k := 1;
while i * i <= n do begin if (n mod i) = 0 then begin inc(Result); var j := n div i; if j <> i then inc(Result); end; inc(i, k); end;
end;
begin
writeln('The tau functions for the first 100 positive integers are:'); for var i := 1 to 100 do begin write(CountDivisors(i): 2, ' '); if (i mod 20) = 0 then writeln; end; readln;
end.</lang>
Dyalect
<lang dyalect>func divisorCount(number) {
var n = number var total = 1 while (n &&& 1) == 0 { total += 1 n >>>= 1 } var p = 3 while p * p <= n { var count = 1 while n % p == 0 { count += 1 n /= p } total *= count p += 2 } if n > 1 { total *= 2 } total
}
let limit = 100 print("Count of divisors for the first \(limit) positive integers:") for n in 1..limit {
print(divisorCount(number: n).toString().padLeft(2, ' ') + " ", terminator: "") print() when n % 20 == 0
}</lang>
- Output:
Count of divisors for the first 100 positive integers: 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
F#
This task uses Extensible Prime Generator (F#).
<lang fsharp>
// Tau function. Nigel Galloway: March 10th., 2021
let tau u=let P=primes32()
let rec fN g=match u%g with 0->g |_->fN(Seq.head P) let rec fG n i g e l=match n=u,u%l with (true,_)->e |(_,0)->fG (n*i) i g (e+g)(l*i) |_->let q=fN(Seq.head P) in fG (n*q) q e (e+e) (q*q) let n=Seq.head P in fG 1 n 1 1 n
[1..100]|>Seq.iter(tau>>printf "%d "); printfn "" </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
Factor
<lang factor>USING: assocs formatting io kernel math math.primes.factors math.ranges sequences sequences.extras ;
ERROR: nonpositive n ;
- (tau) ( n -- count )
group-factors values [ 1 + ] map-product ; inline
- tau ( n -- count ) dup 0 > [ (tau) ] [ nonpositive ] if ;
"Number of divisors for integers 1-100:" print nl " n | tau(n)" print "-----+-----------------------------------------" print 1 100 10 <range> [
[ "%2d |" printf ] [ dup 10 + [a,b) [ tau "%4d" printf ] each nl ] bi
] each</lang>
- Output:
Number of divisors for integers 1-100: n | tau(n) -----+----------------------------------------- 1 | 1 2 2 3 2 4 2 4 3 4 11 | 2 6 2 4 4 5 2 6 2 6 21 | 4 4 2 8 3 4 4 6 2 8 31 | 2 6 4 4 4 9 2 4 4 8 41 | 2 8 2 6 6 4 2 10 3 6 51 | 4 6 2 8 4 8 4 4 2 12 61 | 2 4 6 7 4 8 2 6 4 8 71 | 2 12 2 4 6 6 4 8 2 10 81 | 5 4 2 12 4 4 4 8 2 12 91 | 4 6 4 4 4 12 2 6 6 9
Fermat
<lang>Func Tau(t) =
if t<3 then Return(t) else numdiv:=2; for q = 2 to t\2 do if Divides(q, t) then numdiv:=numdiv+1 fi; od; Return(numdiv); fi; .;
for i = 1 to 100 do
!(Tau(i),' ');
od;</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
Forth
<lang forth>: divisor_count ( n -- n )
1 >r begin dup 2 mod 0= while r> 1+ >r 2/ repeat 3 begin 2dup dup * >= while 1 >r begin 2dup mod 0= while r> 1+ >r tuck / swap repeat 2r> * >r 2 + repeat drop 1 > if r> 2* else r> then ;
- print_divisor_counts ( n -- )
." Count of divisors for the first " dup . ." positive integers:" cr 1+ 1 do i divisor_count 2 .r i 20 mod 0= if cr else space then loop ;
100 print_divisor_counts bye</lang>
- Output:
Count of divisors for the first 100 positive integers: 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
FreeBASIC
<lang freebasic>function numdiv( n as uinteger ) as uinteger
dim as uinteger c = 1 for i as uinteger = 1 to (n+1)\2 if n mod i = 0 then c += 1 next i if n=1 then c-=1 return c
end function
for i as uinteger = 1 to 100
print numdiv(i), if i mod 10 = 0 then print
next i</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
Go
<lang go>package main
import "fmt"
func countDivisors(n int) int {
count := 0 i := 1 k := 2 if n%2 == 0 { k = 1 } for i*i <= n { if n%i == 0 { count++ j := n / i if j != i { count++ } } i += k } return count
}
func main() {
fmt.Println("The tau functions for the first 100 positive integers are:") for i := 1; i <= 100; i++ { fmt.Printf("%2d ", countDivisors(i)) if i%20 == 0 { fmt.Println() } }
}</lang>
- Output:
The tau functions for the first 100 positive integers are: 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
GW-BASIC
<lang gwbasic>10 FOR N = 1 TO 100 20 IF N < 3 THEN T=N: GOTO 70 30 T=2 40 FOR A = 2 TO INT( (N+1)/2 ) 50 IF N MOD A = 0 THEN T = T + 1 60 NEXT A 70 PRINT T; 80 IF N MOD 10 = 0 THEN PRINT 90 NEXT N</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
Haskell
<lang Haskell>tau :: Integral a => a -> a tau n | n <= 0 = error "Not a positive integer" tau n = go 0 (1, 1)
where yo i = (i, i * i) go r (i, ii) | n < ii = r | n == ii = r + 1 | 0 == mod n i = go (r + 2) (yo $ i + 1) | otherwise = go r (yo $ i + 1)
main = print $ map tau [1..100]</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]
Java
<lang java>public class TauFunction {
private static long divisorCount(long n) { long total = 1; // Deal with powers of 2 first for (; (n & 1) == 0; n >>= 1) { ++total; } // Odd prime factors up to the square root for (long p = 3; p * p <= n; p += 2) { long count = 1; for (; n % p == 0; n /= p) { ++count; } total *= count; } // If n > 1 then it's prime if (n > 1) { total *= 2; } return total; }
public static void main(String[] args) { final int limit = 100; System.out.printf("Count of divisors for the first %d positive integers:\n", limit); for (long n = 1; n <= limit; ++n) { System.out.printf("%3d", divisorCount(n)); if (n % 20 == 0) { System.out.println(); } } }
}</lang>
- Output:
Count of divisors for the first 100 positive integers: 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
jq
Works with gojq, the Go implementation of jq
Preliminaries See https://rosettacode.org/wiki/Sum_of_divisors#jq for the definition of `divisors` used here.<lang jq>def count(s): reduce s as $x (0; .+1);
- For pretty-printing
def nwise($n):
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end; n;
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;</lang> The task <lang jq>[range(1;101) | count(divisors)] | nwise(10) | map(lpad(4)) | join("")</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
Julia
Recycles code from http://www.rosettacode.org/wiki/Sequence:_smallest_number_greater_than_previous_term_with_exactly_n_divisors#Julia <lang julia>using Primes
function numfactors(n)
f = [one(n)] for (p, e) in factor(n) f = reduce(vcat, [f * p^j for j in 1:e], init = f) end length(f)
end
for i in 1:100
print(rpad(numfactors(i), 3), i % 25 == 0 ? " \n" : " ")
end
</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
Lua
<lang lua>function divisorCount(n)
local total = 1 -- Deal with powers of 2 first while (n & 1) == 0 do total = total + 1 n = math.floor(n / 2) end -- Odd prime factors up tot eh square root local p = 3 while p * p <= n do local count = 1 while n % p == 0 do count = count + 1 n = n / p end total = total * count p = p + 2 end -- If n > 1 then it's prime if n > 1 then total = total * 2 end return total
end
limit = 100 print("Count of divisors for the first " .. limit .. " positive integers:") for n=1,limit do
io.write(string.format("%3d", divisorCount(n))) if n % 20 == 0 then print() end
end</lang>
- Output:
Count of divisors for the first 100 positive integers: 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
Mathematica/Wolfram Language
<lang Mathematica>DivisorSum[#, 1 &] & /@ Range[100]</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}
Modula-2
<lang modula2>MODULE TauFunc; FROM InOut IMPORT WriteCard, WriteLn;
VAR i: CARDINAL;
PROCEDURE tau(n: CARDINAL): CARDINAL;
VAR total, count, p: CARDINAL;
BEGIN
total := 1; WHILE n MOD 2 = 0 DO n := n DIV 2; total := total + 1 END; p := 3; WHILE p*p <= n DO count := 1; WHILE n MOD p = 0 DO n := n DIV p; count := count + 1 END; total := total * count; p := p + 2 END; IF n>1 THEN total := total * 2 END; RETURN total;
END tau;
BEGIN
FOR i := 1 TO 100 DO WriteCard(tau(i), 3); IF i MOD 20 = 0 THEN WriteLn END END
END TauFunc.</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
Nim
<lang Nim>import math, strutils
func divcount(n: Natural): Natural =
for i in 1..sqrt(n.toFloat).int: if n mod i == 0: inc result if n div i != i: inc result
echo "Count of divisors for the first 100 positive integers:" for i in 1..100:
stdout.write ($divcount(i)).align(3) if i mod 20 == 0: echo()</lang>
- Output:
Count of divisors for the first 100 positive integers: 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
PARI/GP
<lang parigp>vector(100,X,numdiv(X))</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]
Pascal
<lang pascal>program tauFunction(output);
type { name starts with `integer…` to facilitate sorting in documentation } integerPositive = 1..maxInt value 1; { the `value …` will initialize all variables to this value }
{ returns Boolean value of the expression divisor ∣ dividend ----------- } function divides( protected divisor: integerPositive; protected dividend: integer ): Boolean; begin { in Pascal, function result variable has the same name as function } divides := dividend mod divisor = 0 end;
{ returns τ(i) --------------------------------------------------------- } function tau(protected i: integerPositive): integerPositive; var count, potentialDivisor: integerPositive; begin { count is initialized to 1 and every number is divisible by one } for potentialDivisor := 2 to i do begin count := count + ord(divides(potentialDivisor, i)) end;
{ in Pascal, there must be exactly one assignment to result variable } tau := count end;
{ === MAIN ============================================================= } var i: integerPositive; f: string(6); begin for i := 1 to 100 do begin writeStr(f, 'τ(', i:1); writeLn(f:8, ') = ', tau(i):5) end end.</lang>
Free Pascal
and on TIO.RUN. Only test 0..99 for a nicer table.
<lang pascal>program Tau_function; {$IFDEF Windows} {$APPTYPE CONSOLE} {$ENDIF}
function CountDivisors(n: NativeUint): integer; var q, p, cnt, divcnt: NativeUint; begin divCnt := 1; if n > 1 then begin cnt := 1; while not (Odd(n)) do begin n := n shr 1; divCnt := divCnt+cnt; end; p := 3; while p * p <= n do begin cnt := divCnt; q := n div p; while q * p = n do begin n := q; q := n div p; divCnt := divCnt+cnt; end; Inc(p, 2); end; if n <> 1 then divCnt := divCnt+divCnt; end; CountDivisors := divCnt; end;
const
UPPERLIMIT = 99; colWidth = trunc(ln(UPPERLIMIT)/ln(10))+1;
var
i: NativeUint;
begin
writeln('The tau functions for the first ',UPPERLIMIT,' positive integers are:'); Write(: colWidth+1); for i := 0 to 9 do Write(i: colWidth, ' '); for i := 0 to UPPERLIMIT do begin if i mod 10 = 0 then begin writeln; Write(i div 10: colWidth, '|'); end; Write(CountDivisors(i): colWidth, ' '); end; writeln; {$Ifdef Windows}readln;{$ENDIF}
end.</lang>
- TIO.RUN:
The tau functions for the first 99 positive integers are: 0 1 2 3 4 5 6 7 8 9 0| 1 1 2 2 3 2 4 2 4 3 1| 4 2 6 2 4 4 5 2 6 2 2| 6 4 4 2 8 3 4 4 6 2 3| 8 2 6 4 4 4 9 2 4 4 4| 8 2 8 2 6 6 4 2 10 3 5| 6 4 6 2 8 4 8 4 4 2 6|12 2 4 6 7 4 8 2 6 4 7| 8 2 12 2 4 6 6 4 8 2 8|10 5 4 2 12 4 4 4 8 2 9|12 4 6 4 4 4 12 2 6 6
Perl
<lang perl>use strict; use warnings; use feature 'say'; use ntheory 'divisors';
my @x; push @x, scalar divisors($_) for 1..100;
say "Tau function - first 100:\n" .
((sprintf "@{['%4d' x 100]}", @x[0..100-1]) =~ s/(.{80})/$1\n/gr);</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
Phix
imperative
for i=1 to 100 do printf(1,"%3d",{length(factors(i,1))}) if remainder(i,20)=0 then puts(1,"\n") end if end for
- 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
functional
same output
sequence r = apply(apply(true,factors,{tagset(100),{1}}),length) puts(1,join_by(apply(true,sprintf,{{"%3d"},r}),1,20,""))
PureBasic
<lang PureBasic>If OpenConsole()
For i=1 To 100 If i<3 : Print(RSet(Str(i),4)) : Continue :EndIf c=2 For j=2 To i/2+1 : c+Bool(i%j=0) : Next Print(RSet(Str(c),4)) If i%10=0 : PrintN("") : EndIf Next Input()
EndIf End</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
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]
Choosing the right abstraction
Yet another exercise in defining a divisors function.
<lang python>The number of divisors of n
from itertools import count, islice from math import floor, sqrt
- oeisA000005 :: [Int]
def oeisA000005():
tau(n) (also called d(n) or sigma_0(n)), the number of divisors of n. return map(tau, count(1))
- tau :: Int -> Int
def tau(n):
The number of divisors of n. return len(divisors(n))
- ------------------------- TEST -------------------------
- main :: IO ()
def main():
The first 100 terms of OEIS A000005. (Shown in rows of 10) terms = take(100)( oeisA000005() ) columnWidth = 1 + len(str(max(terms)))
print( '\n'.join( .join( str(term).rjust(columnWidth) for term in row ) for row in chunksOf(10)(terms) ) )
- ----------------------- GENERIC ------------------------
- chunksOf :: Int -> [a] -> a
def chunksOf(n):
A series of lists of length n, subdividing the contents of xs. Where the length of xs is not evenly divible, the final list will be shorter than n. def go(xs): return [ xs[i:n + i] for i in range(0, len(xs), n) ] if 0 < n else None return go
- divisors :: Int -> [Int]
def divisors(n):
List of all divisors of n including n itself. root = floor(sqrt(n)) lows = [x for x in range(1, 1 + root) if 0 == n % x] return lows + [n // x for x in reversed(lows)][ (1 if n == (root * root) else 0): ]
- take :: Int -> [a] -> [a]
- take :: Int -> String -> String
def take(n):
The prefix of xs of length n, or xs itself if n > length xs. def go(xs): return ( xs[0:n] if isinstance(xs, (list, tuple)) else list(islice(xs, n)) ) return go
- MAIN ---
if __name__ == '__main__':
main()</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
Quackery
factors
is defined at Factors of an integer#Quackery.
<lang Quackery> [ factors size ] is tau ( n --> n )
[] [] 100 times [ i^ 1+ tau join ] witheach [ number$ nested join ] 70 wrap$
</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
R
This only takes one line. <lang rsplus>lengths(sapply(1:100, function(n) c(Filter(function(x) n %% x == 0, seq_len(n %/% 2)), n)))</lang>
Raku
Yet more tasks that are tiny variations of each other. Tau function, Tau number, Sum of divisors and Product of divisors all use code with minimal changes. What the heck, post 'em all.
<lang perl6>use Prime::Factor:ver<0.3.0+>; use Lingua::EN::Numbers;
say "\nTau function - first 100:\n", # ID (1..*).map({ +.&divisors })[^100]\ # the task .batch(20)».fmt("%3d").join("\n"); # display formatting
say "\nTau numbers - first 100:\n", # ID (1..*).grep({ $_ %% +.&divisors })[^100]\ # the task .batch(10)».&comma».fmt("%5s").join("\n"); # display formatting
say "\nDivisor sums - first 100:\n", # ID (1..*).map({ [+] .&divisors })[^100]\ # the task .batch(20)».fmt("%4d").join("\n"); # display formatting
say "\nDivisor products - first 100:\n", # ID (1..*).map({ [×] .&divisors })[^100]\ # the task .batch(5)».&comma».fmt("%16s").join("\n"); # display formatting</lang>
- Output:
Tau function - first 100: 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 Tau numbers - first 100: 1 2 8 9 12 18 24 36 40 56 60 72 80 84 88 96 104 108 128 132 136 152 156 180 184 204 225 228 232 240 248 252 276 288 296 328 344 348 360 372 376 384 396 424 441 444 448 450 468 472 480 488 492 504 516 536 560 564 568 584 600 612 625 632 636 640 664 672 684 708 712 720 732 776 792 804 808 824 828 852 856 864 872 876 880 882 896 904 936 948 972 996 1,016 1,040 1,044 1,048 1,056 1,068 1,089 1,096 Divisor sums - first 100: 1 3 4 7 6 12 8 15 13 18 12 28 14 24 24 31 18 39 20 42 32 36 24 60 31 42 40 56 30 72 32 63 48 54 48 91 38 60 56 90 42 96 44 84 78 72 48 124 57 93 72 98 54 120 72 120 80 90 60 168 62 96 104 127 84 144 68 126 96 144 72 195 74 114 124 140 96 168 80 186 121 126 84 224 108 132 120 180 90 234 112 168 128 144 120 252 98 171 156 217 Divisor products - first 100: 1 2 3 8 5 36 7 64 27 100 11 1,728 13 196 225 1,024 17 5,832 19 8,000 441 484 23 331,776 125 676 729 21,952 29 810,000 31 32,768 1,089 1,156 1,225 10,077,696 37 1,444 1,521 2,560,000 41 3,111,696 43 85,184 91,125 2,116 47 254,803,968 343 125,000 2,601 140,608 53 8,503,056 3,025 9,834,496 3,249 3,364 59 46,656,000,000 61 3,844 250,047 2,097,152 4,225 18,974,736 67 314,432 4,761 24,010,000 71 139,314,069,504 73 5,476 421,875 438,976 5,929 37,015,056 79 3,276,800,000 59,049 6,724 83 351,298,031,616 7,225 7,396 7,569 59,969,536 89 531,441,000,000 8,281 778,688 8,649 8,836 9,025 782,757,789,696 97 941,192 970,299 1,000,000,000
REXX
<lang rexx>/*REXX program counts the number of divisors (tau, or sigma_0) up to and including N.*/ parse arg LO HI cols . /*obtain optional argument from the CL.*/ if LO== | LO=="," then LO= 1 /*Not specified? Then use the default.*/ if HI== | HI=="," then HI= LO + 100 - 1 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 20 /* " " " " " " */ w= 2 + (HI>45359) /*W: used to align the output columns.*/ say 'The number of divisors (tau) for integers up to ' n " (inclusive):"; say say '─index─' center(" tau (number of divisors) ", cols * (w+1) + 1, '─') $=; c= 0 /*$: the output list, shown ROW/line.*/
do j=LO to HI; c= c + 1 /*list # proper divisors (tau) 1 ──► N */ $= $ right( tau(j), w) /*add a tau number to the output list. */ if c//cols \== 0 then iterate /*Not a multiple of ROW? Don't display.*/ idx= j - cols + 1 /*calculate index value (for this row).*/ say center(idx, 7) $; $= /*display partial list to the terminal.*/ end /*j*/
if $\== then say center(idx+cols, 7) $ /*there 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 #= 2 /*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*/; return # /* [↑] 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
Ring
<lang ring> see "The tau functions for the first 100 positive integers are:" + nl
n = 0 num = 0 limit = 100 while num < limit
n = n + 1 tau = 0 for m = 1 to n if n%m = 0 tau = tau + 1 ok next num = num + 1 if num%10 = 1 see nl ok tau = string(tau) if len(tau) = 1 tau = " " + tau ok see "" + tau + " "
end </lang> Output:
The tau functions for the first 100 positive integers are: 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
Ruby
<lang ruby>require 'prime'
def tau(n) = n.prime_division.inject(1){|res, (d, exp)| res *= exp + 1}
(1..100).map{|n| tau(n).to_s.rjust(3) }.each_slice(20){|ar| puts ar.join} </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
Rust
<lang rust>// returns the highest power of i that is a factor of n, // and n divided by that power of i fn factor_exponent(n: i32, i: i32) -> (i32, i32) { if n % i == 0 { let (a, b) = factor_exponent(n / i, i); (a + 1, b) } else { (0, n) } }
fn tau(n: i32) -> i32 { for i in 2..(n+1) { if n % i == 0 { let (count, next) = factor_exponent(n, i); return (count + 1) * tau(next); } } return 1; }
fn main() { for i in 1..101 { print!("{} ", tau(i)); } }</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
Sidef
Built-in: <lang ruby>say { .sigma0 }.map(1..100).join(' ')</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
Swift
<lang swift>import Foundation
// See https://en.wikipedia.org/wiki/Divisor_function func divisorCount(number: Int) -> Int {
var n = number var total = 1 // Deal with powers of 2 first while (n & 1) == 0 { total += 1 n >>= 1 } // Odd prime factors up to the square root var p = 3 while p * p <= n { var count = 1 while n % p == 0 { count += 1 n /= p } total *= count p += 2 } // If n > 1 then it's prime if n > 1 { total *= 2 } return total
}
let limit = 100 print("Count of divisors for the first \(limit) positive integers:") for n in 1...limit {
print(String(format: "%3d", divisorCount(number: n)), terminator: "") if n % 20 == 0 { print() }
}</lang>
- Output:
Count of divisors for the first 100 positive integers: 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
Tiny BASIC
<lang tinybasic> LET N = 0
10 LET N = N + 1 IF N < 3 THEN GOTO 100 LET T = 2 LET A = 1 20 LET A = A + 1 IF (N/A)*A = N THEN LET T = T + 1 IF A<(N+1)/2 THEN GOTO 20 30 PRINT "Tau(",N,") = ",T IF N<100 THEN GOTO 10 END
100 LET T = N
GOTO 30</lang>
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt
System.print("The tau functions for the first 100 positive integers are:") for (i in 1..100) {
Fmt.write("$2d ", Int.divisors(i).count) if (i % 20 == 0) System.print()
}</lang>
- Output:
The tau functions for the first 100 positive integers are: 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
- Programming Tasks
- Solutions by Programming Task
- Mathematics
- 11l
- Action!
- ALGOL W
- AppleScript
- Arturo
- AWK
- BASIC
- BCPL
- C
- C++
- CLU
- COBOL
- Cowgol
- D
- Delphi
- System.SysUtils
- Dyalect
- F Sharp
- Factor
- Fermat
- Forth
- FreeBASIC
- Go
- GW-BASIC
- Haskell
- Java
- Jq
- Julia
- Lua
- Mathematica
- Wolfram Language
- Modula-2
- Nim
- PARI/GP
- Pascal
- Free Pascal
- Perl
- Ntheory
- Phix
- PureBasic
- Python
- Quackery
- R
- Raku
- REXX
- Ring
- Ruby
- Rust
- Sidef
- Swift
- Tiny BASIC
- Wren
- Wren-math
- Wren-fmt