Anti-primes

Anti-primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The anti-primes (or highly composite numbers) are the natural numbers with more factors than any smaller than itself.

Task

Generate and show here, the first twenty anti-primes.

Related task

•   Factors of an integer

C

Translation of: Go

<lang c>#include <stdio.h>

int countDivisors(int n) {

   int i, count;
   if (n < 2) return 1;
   count = 2; // 1 and n
   for (i = 2; i <= n/2; ++i) {
       if (n%i == 0) ++count;
   }
   return count;

}

int main() {

   int n, d, maxDiv = 0, count = 0;
   printf("The first 20 anti-primes are:\n");
   for (n = 1; count < 20; ++n) {
       d = countDivisors(n); 
       if (d > maxDiv) {
           printf("%d ", n);
           maxDiv = d;
           count++;
       }
   }
   printf("\n"); 
   return 0;

}</lang>

Output:

The first 20 anti-primes are:
1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560 

Go

Simple brute force approach which is quick enough here. <lang go>package main

import "fmt"

func countDivisors(n int) int {

   if n < 2 {
       return 1
   }
   count := 2 // 1 and n
   for i := 2; i <= n/2; i++ {
       if n%i == 0 {
           count++
       }
   }
   return count

}

func main() {

   fmt.Println("The first 20 anti-primes are:")
   maxDiv := 0
   count := 0
   for n := 1; count < 20; n++ {
       d := countDivisors(n)
       if d > maxDiv {
           fmt.Printf("%d ", n)
           maxDiv = d
           count++
       }
   }
   fmt.Println()

}</lang>

Output:

The first 20 anti-primes are:
1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560 

Pascal

Easy factoring without primes.Decided to show count of factors. <lang pascal>program AntiPrimes; {$IFdef FPC}

 {$MOde Delphi}

{$IFEND} function getFactorCnt(n:NativeUint):NativeUint; var

 divi,quot,pot,lmt : NativeUint;

begin

 result := 1;
 divi  := 1;
 lmt := trunc(sqrt(n));
 while divi < n do
 Begin
   inc(divi);
   pot := 0;
   repeat
     quot := n div divi;
     if n <> quot*divi then
       BREAK;
     n := quot;
     inc(pot);
   until false;
   result := result*(1+pot);
   //IF n= prime leave now
   if divi > lmt then
     BREAK;
 end;

end;

var

 i,Count,FacCnt,lastCnt: NativeUint;

begin

 count := 0;
 lastCnt := 0;
 i := 1;
 repeat
   FacCnt := getFactorCnt(i);
   if  lastCnt < FacCnt then
   Begin
     write(i,'(',FacCnt,'),');
     lastCnt:= FacCnt;
     inc(Count);
     if count = 12 then
       Writeln;
   end;
   inc(i);
 until Count >= 20;
 writeln;

end.</lang>;Output:

1(1),2(2),4(3),6(4),12(6),24(8),36(9),48(10),60(12),120(16),180(18),240(20),
360(24),720(30),840(32),1260(36),1680(40),2520(48),5040(60),7560(64)

Perl 6

Works with: Rakudo version 2018.11

At its heart, this task is almost exactly the same as Proper_Divisors, it is just asking for slightly different results. Much of this code is lifted straight from there.

Implemented as an auto-extending lazy list. Displaying the count of anti-primes less than 5e5 also because... why not.

<lang perl6>sub propdiv (\x) {

   my @l = 1 if x > 1;
   (2 .. x.sqrt.floor).map: -> \d {
       unless x % d { @l.push: d; my \y = x div d; @l.push: y if y != d }
   }
   @l

}

my atomicint $last = 0;

my @anti-primes = lazy 1, |(|(2..59), 60, *+30 … *).hyper.grep: -> $c {

   my \mx = +propdiv($c);
   next if mx <= $last;
   $last = mx;
   $c

}

my $upto = 5e5;

put "First 20 anti-primes:\n{ @anti-primes[^20] }";

put "\nCount of anti-primes <= $upto: {+@anti-primes[^(@anti-primes.first: * > $upto, :k)]}";</lang>

Output:

First 20 anti-primes:
1 2 4 6 12 24 36 48 60 120 180 240 360 720 840 1260 1680 2520 5040 7560

Count of anti-primes <= 500000: 36

Python

Uses the fast prime function from Factors of an integer#Python <lang python>from itertools import chain, count, cycle, islice, accumulate

def factors(n):

   def prime_powers(n):
       for c in accumulate(chain([2, 1, 2], cycle([2,4]))):
           if c*c > n: break
           if n%c: continue
           d,p = (), c
           while not n%c:
               n,p,d = n//c, p*c, d + (p,)
           yield(d)
       if n > 1: yield((n,))

   r = [1]
   for e in prime_powers(n):
       r += [a*b for a in r for b in e]
   return r
   

def antiprimes():

   mx = 0
   for c in count(1):
       ln = len(factors(c))
       if ln > mx:
           yield c
           mx = ln        

if __name__ == '__main__':

   print(list(islice(antiprimes(), 20)))</lang>

Output:

[1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560]

Sidef

Using the built-in Number.sigma0 method to count the number of divisors. <lang ruby>say with (0) {|max|

   1..Inf -> lazy.grep { (.sigma0 > max) && (max = .sigma0) }.first(20)

}</lang>

Output:

[1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560]