Sequence: smallest number greater than previous term with exactly n divisors: Difference between revisions
Realize in F# |
Added Swift solution |
||
Line 997: | Line 997: | ||
<pre> |
<pre> |
||
[1, 2, 4, 6, 16, 18, 64, 66, 100, 112, 1024, 1035, 4096, 4288, 4624] |
[1, 2, 4, 6, 16, 18, 64, 66, 100, 112, 1024, 1035, 4096, 4288, 4624] |
||
</pre> |
|||
=={{header|Swift}}== |
|||
Includes an optimization borrowed from the Pascal example above. |
|||
<lang swift>// 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 % 2 == 0 { |
|||
total += 1 |
|||
n /= 2 |
|||
} |
|||
// 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 = 32 |
|||
var n = 1 |
|||
var next = 1 |
|||
while next <= limit { |
|||
if next == divisorCount(number: n) { |
|||
print(n, terminator: " ") |
|||
next += 1 |
|||
if next > 4 && divisorCount(number: next) == 2 { |
|||
n = 1 << (next - 1) - 1; |
|||
} |
|||
} |
|||
n += 1 |
|||
} |
|||
print()</lang> |
|||
{{out}} |
|||
<pre> |
|||
1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624 4632 65536 65572 262144 262192 263169 269312 4194304 4194306 4477456 4493312 4498641 4498752 268435456 268437200 1073741824 1073741830 |
|||
</pre> |
</pre> |
||
Revision as of 22:14, 19 July 2020
You are encouraged to solve this task according to the task description, using any language you may know.
Calculate the sequence where each term an is the smallest natural number greater than the previous term, that has exactly n divisors.
- Task
Show here, on this page, at least the first 15 terms of the sequence.
- See also
- Related tasks
Ada
<lang Ada>with Ada.Text_IO;
procedure Show_Sequence is
function Count_Divisors (N : in Natural) return Natural is Count : Natural := 0; I : Natural; begin I := 1; while I**2 <= N loop if N mod I = 0 then if I = N / I then Count := Count + 1; else Count := Count + 2; end if; end if; I := I + 1; end loop;
return Count; end Count_Divisors;
procedure Show (Max : in Natural) is use Ada.Text_IO; N : Natural := 1; Begin Put_Line ("The first" & Max'Image & "terms of the sequence are:"); for Divisors in 1 .. Max loop while Count_Divisors (N) /= Divisors loop N := N + 1; end loop; Put (N'Image); end loop; New_Line; end Show;
begin
Show (15);
end Show_Sequence;</lang>
- Output:
The first 15terms of the sequence are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
ALGOL 68
<lang algol68>BEGIN
PROC count divisors = ( INT n )INT: BEGIN INT count := 0; FOR i WHILE i*i <= n DO IF n MOD i = 0 THEN count +:= IF i = n OVER i THEN 1 ELSE 2 FI FI OD; count END # count divisors # ; INT max = 15;
print( ( "The first ", whole( max, 0 ), " terms of the sequence are:", newline ) ); INT next := 1; FOR i WHILE next <= max DO IF next = count divisors( i ) THEN print( ( whole( i, 0 ), " " ) ); next +:= 1 FI OD; print( ( newline, newline ) )
END</lang>
- Output:
The first 15 terms of the sequence are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
AWK
<lang AWK>
- syntax: GAWK -f SEQUENCE_SMALLEST_NUMBER_GREATER_THAN_PREVIOUS_TERM_WITH_EXACTLY_N_DIVISORS.AWK
- converted from Kotlin
BEGIN {
limit = 15 printf("first %d terms:",limit) n = 1 while (n <= limit) { if (n == count_divisors(++i)) { printf(" %d",i) n++ } } 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:
first 15 terms: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
C
<lang c>#include <stdio.h>
- define MAX 15
int count_divisors(int n) {
int i, count = 0; for (i = 1; i * i <= n; ++i) { if (!(n % i)) { if (i == n / i) count++; else count += 2; } } return count;
}
int main() {
int i, next = 1; printf("The first %d terms of the sequence are:\n", MAX); for (i = 1; next <= MAX; ++i) { if (next == count_divisors(i)) { printf("%d ", i); next++; } } printf("\n"); return 0;
}</lang>
- Output:
The first 15 terms of the sequence are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
C++
<lang cpp>#include <iostream>
- define MAX 15
using namespace std;
int count_divisors(int n) {
int count = 0; for (int i = 1; i * i <= n; ++i) { if (!(n % i)) { if (i == n / i) count++; else count += 2; } } return count;
}
int main() {
cout << "The first " << MAX << " terms of the sequence are:" << endl; for (int i = 1, next = 1; next <= MAX; ++i) { if (next == count_divisors(i)) { cout << i << " "; next++; } } cout << endl; return 0;
}</lang>
- Output:
The first 15 terms of the sequence are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
Alternative
More terms and quicker than the straightforward C version above. Try It Online!<lang cpp>#include <cstdio>
- include <chrono>
using namespace std::chrono;
const int MAX = 32;
unsigned int getDividersCnt(unsigned int n) {
unsigned int d = 3, q, dRes, res = 1; while (!(n & 1)) { n >>= 1; res++; } while ((d * d) <= n) { q = n / d; if (n % d == 0) { dRes = 0; do { dRes += res; n = q; q /= d; } while (n % d == 0); res += dRes; } d += 2; } return n != 1 ? res << 1 : res; }
int main() { unsigned int i, nxt, DivCnt;
printf("The first %d anti-primes plus are: ", MAX); auto st = steady_clock::now(); i = nxt = 1; do { if ((DivCnt = getDividersCnt(i)) == nxt ) { printf("%d ", i); if ((++nxt > 4) && (getDividersCnt(nxt) == 2)) i = (1 << (nxt - 1)) - 1; } i++; } while (nxt <= MAX); printf("%d ms", (int)(duration<double>(steady_clock::now() - st).count() * 1000));
}</lang>
- Output:
The first 32 anti-primes plus are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624 4632 65536 65572 262144 262192 263169 269312 4194304 4194306 4477456 4493312 4498641 4498752 268435456 268437200 1073741824 1073741830 223 ms
Dyalect
<lang dyalect>func countDivisors(n) {
var count = 0 var i = 1 while i * i <= n { if n % i == 0 { if i == n / i { count += 1 } else { count += 2 } } i += 1 } return count
}
const max = 15 print("The first \(max) terms of the sequence are:") var (i, next) = (1, 1) while next <= max {
if next == countDivisors(i) { print("\(i) ", terminator = "") next += 1 } i += 1
}
print()</lang>
- Output:
The first 15 terms of the sequence are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
F#
First 28 are easy with a Naive implementation
<lang fsharp> // Nigel Galloway: November 19th., 2017 let fN g=[1..(float>>sqrt>>int)g]|>List.fold(fun Σ n->if g%n>0 then Σ else if g/n=n then Σ+1 else Σ+2) 0 let A069654=let rec fG n g=seq{match g-fN n with 0->yield n; yield! fG(n+1)(g+1) |_->yield! fG(n+1)g} in fG 1 1
A069654 |> Seq.take 28|>Seq.iter(printf "%d "); printfn "" </lang>
- Output:
1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624 4632 65536 65572 262144 262192 263169 269312 4194304 4194306 4477456 4493312 4498641 4498752
Factor
<lang factor>USING: io kernel math math.primes.factors prettyprint sequences ;
- next ( n num -- n' num' )
[ 2dup divisors length = ] [ 1 + ] do until [ 1 + ] dip ;
- A069654 ( n -- seq )
[ 2 1 ] dip [ [ next ] keep ] replicate 2nip ;
"The first 15 terms of the sequence are:" print 15 A069654 .</lang>
- Output:
The first 15 terms of the sequence are: { 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624 }
Go
<lang go>package main
import "fmt"
func countDivisors(n int) int {
count := 0 for i := 1; i*i <= n; i++ { if n%i == 0 { if i == n/i { count++ } else { count += 2 } } } return count
}
func main() {
const max = 15 fmt.Println("The first", max, "terms of the sequence are:") for i, next := 1, 1; next <= max; i++ { if next == countDivisors(i) { fmt.Printf("%d ", i) next++ } } fmt.Println()
}</lang>
- Output:
The first 15 terms of the sequence are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
Haskell
<lang haskell>import Text.Printf (printf)
sequence_A069654 :: [(Int,Int)] sequence_A069654 = go 1 $ (,) <*> countDivisors <$> [1..]
where go t ((n,c):xs) | c == t = (t,n):go (succ t) xs | otherwise = go t xs countDivisors n = foldr f 0 [1..floor $ sqrt $ realToFrac n] where f x r | n `mod` x == 0 = if n `div` x == x then r+1 else r+2 | otherwise = r
main :: IO () main = mapM_ (uncurry $ printf "a(%2d)=%5d\n") $ take 15 sequence_A069654</lang>
- Output:
a( 1)= 1 a( 2)= 2 a( 3)= 4 a( 4)= 6 a( 5)= 16 a( 6)= 18 a( 7)= 64 a( 8)= 66 a( 9)= 100 a(10)= 112 a(11)= 1024 a(12)= 1035 a(13)= 4096 a(14)= 4288 a(15)= 4624
J
<lang j> sieve=: 3 :0
NB. sieve y returns a vector of y boxes. NB. In each box is an array of 2 columns. NB. The first column is the factor tally NB. and the second column is a number with NB. that many factors. NB. Rather than factoring, the algorithm NB. counts prime seive cell hits. NB. The boxes are not ordered by factor tally. range=. <. + i.@:|@:- tally=. y#0 for_i.#\tally do. j=. }:^:(y<:{:)i * 1 range >: <. y % i tally=. j >:@:{`[`]} tally end. (</.~ {."1) (,. i.@:#)tally
) </lang>
A=: sieve 100000 B=: /:~ A missing=: [: (-.~i.@:#) (<0 0)&{&> C=: ({.~ {.@:missing) B D=:{:"1 L:_1 C (] , [ {~ (I. {:))&.>/@:|. D +-----------------------------------------------------------------------+ |0 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624 4632 65536 65572| +-----------------------------------------------------------------------+
Intermediate steps and explanation for a smaller sieve:
] A=: sieve 60 +---+---+----+----+----+----+----+----+----+-----+ |0 0|1 1|2 2|3 4|4 6|6 12|5 16|8 24|9 36|10 48| | | |2 3|3 9|4 8|6 18| |8 30| | | | | |2 5|3 25|4 10|6 20| |8 40| | | | | |2 7|3 49|4 14|6 28| |8 42| | | | | |2 11| |4 15|6 32| |8 54| | | | | |2 13| |4 21|6 44| |8 56| | | | | |2 17| |4 22|6 45| | | | | | | |2 19| |4 26|6 50| | | | | | | |2 23| |4 27|6 52| | | | | | | |2 29| |4 33| | | | | | | | |2 31| |4 34| | | | | | | | |2 37| |4 35| | | | | | | | |2 41| |4 38| | | | | | | | |2 43| |4 39| | | | | | | | |2 47| |4 46| | | | | | | | |2 53| |4 51| | | | | | | | |2 59| |4 55| | | | | | | | | | |4 57| | | | | | | | | | |4 58| | | | | | +---+---+----+----+----+----+----+----+----+-----+ ] B=: /:~ A NB. ascending sort by tally +---+---+----+----+----+----+----+----+----+-----+ |0 0|1 1|2 2|3 4|4 6|5 16|6 12|8 24|9 36|10 48| | | |2 3|3 9|4 8| |6 18|8 30| | | | | |2 5|3 25|4 10| |6 20|8 40| | | | | |2 7|3 49|4 14| |6 28|8 42| | | | | |2 11| |4 15| |6 32|8 54| | | | | |2 13| |4 21| |6 44|8 56| | | | | |2 17| |4 22| |6 45| | | | | | |2 19| |4 26| |6 50| | | | | | |2 23| |4 27| |6 52| | | | | | |2 29| |4 33| | | | | | | | |2 31| |4 34| | | | | | | | |2 37| |4 35| | | | | | | | |2 41| |4 38| | | | | | | | |2 43| |4 39| | | | | | | | |2 47| |4 46| | | | | | | | |2 53| |4 51| | | | | | | | |2 59| |4 55| | | | | | | | | | |4 57| | | | | | | | | | |4 58| | | | | | +---+---+----+----+----+----+----+----+----+-----+ NB. truncate to the fully populated length NB. missing lists the unavailable factor tallies missing=: [: (-.~i.@:#) (<0 0)&{&> ] C=: ({.~ {.@:missing) B NB. retain tally counts with no holes +---+---+----+----+----+----+----+ |0 0|1 1|2 2|3 4|4 6|5 16|6 12| | | |2 3|3 9|4 8| |6 18| | | |2 5|3 25|4 10| |6 20| | | |2 7|3 49|4 14| |6 28| | | |2 11| |4 15| |6 32| | | |2 13| |4 21| |6 44| | | |2 17| |4 22| |6 45| | | |2 19| |4 26| |6 50| | | |2 23| |4 27| |6 52| | | |2 29| |4 33| | | | | |2 31| |4 34| | | | | |2 37| |4 35| | | | | |2 41| |4 38| | | | | |2 43| |4 39| | | | | |2 47| |4 46| | | | | |2 53| |4 51| | | | | |2 59| |4 55| | | | | | | |4 57| | | | | | | |4 58| | | +---+---+----+----+----+----+----+ NB. Remove the tally column from each box (by retaining the values) ,.L:_1 D=:{:"1 L:_1 C +-+-+--+--+--+--+--+ |0|1| 2| 4| 6|16|12| | | | 3| 9| 8| |18| | | | 5|25|10| |20| | | | 7|49|14| |28| | | |11| |15| |32| | | |13| |21| |44| | | |17| |22| |45| | | |19| |26| |50| | | |23| |27| |52| | | |29| |33| | | | | |31| |34| | | | | |37| |35| | | | | |41| |38| | | | | |43| |39| | | | | |47| |46| | | | | |53| |51| | | | | |59| |55| | | | | | | |57| | | | | | | |58| | | +-+-+--+--+--+--+--+ NB. finally enlist successively larger values (] , [ {~ (I. {:))&.>/@:|. D +---------------+ |0 1 2 4 6 16 18| +---------------+
Java
<lang java>public class AntiPrimesPlus {
static int count_divisors(int n) { int count = 0; for (int i = 1; i * i <= n; ++i) { if (n % i == 0) { if (i == n / i) count++; else count += 2; } } return count; }
public static void main(String[] args) { final int max = 15; System.out.printf("The first %d terms of the sequence are:\n", max); for (int i = 1, next = 1; next <= max; ++i) { if (next == count_divisors(i)) { System.out.printf("%d ", i); next++; } } System.out.println(); }
}</lang>
- Output:
The first 15 terms of the sequence are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
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
function A06954(N)
println("First $N terms of OEIS sequence A069654: ") k = 0 for i in 1:N j = k while (j += 1) > 0 if i == numfactors(j) print("$j ") k = j break end end end
end
A06954(15)
</lang>
- Output:
First 15 terms of OEIS sequence A069654: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
Kotlin
<lang scala>// Version 1.3.21
const val MAX = 15
fun countDivisors(n: Int): Int {
var count = 0 var i = 1 while (i * i <= n) { if (n % i == 0) { count += if (i == n / i) 1 else 2 } i++ } return count
}
fun main() {
println("The first $MAX terms of the sequence are:") var i = 1 var next = 1 while (next <= MAX) { if (next == countDivisors(i)) { print("$i ") next++ } i++ } println()
}</lang>
- Output:
The first 15 terms of the sequence are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
Nim
<lang nim>import strformat
const MAX = 15
func countDivisors(n: int): int =
var i = 1 var count = 0 while i * i <= n: if n mod i == 0: if i == n div i: inc count else: inc count, 2 inc i count
var i, next = 1 echo fmt"The first {MAX} terms of the sequence are:" while next <= MAX:
if next == countDivisors(i): write(stdout, fmt"{i} ") inc next inc i
write(stdout, "\n")</lang>
- Output:
The first 15 terms of the sequence are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
Pascal
Counting divisors by prime factorisation.
If divCnt= Count of divisors is prime then the only candidate ist n = prime^(divCnt-1).
There will be more rules. If divCnt is odd then the divisors of divCnt are a^(even_factor*i)*..*k^(even_factor*j).
I think of next = 33 aka 11*3 with the solution 1031^2 * 2^10=1,088,472,064 with a big distance to next= 32 => 1073741830.
Try it online!
<lang pascal>program AntiPrimesPlus;
{$IFDEF FPC}
{$MODE Delphi}
{$ELSE}
{$APPTYPE CONSOLE} // delphi
{$ENDIF} uses
sysutils,math;
const
MAX =32;
function getDividersCnt(n:Uint32):Uint32; // getDividersCnt by dividing n into its prime factors // aka n = 2250 = 2^1*3^2*5^3 has (1+1)*(2+1)*(3+1)= 24 dividers var
divi,quot,deltaRes,rest : Uint32;
begin
result := 1; //divi := 2; //separat without division while Not(Odd(n)) do Begin n := n SHR 1; inc(result); end; //from now on only odd numbers divi := 3; while (sqr(divi)<=n) do Begin DivMod(n,divi,quot,rest); if rest = 0 then Begin deltaRes := 0; repeat inc(deltaRes,result); n := quot; DivMod(n,divi,quot,rest); until rest <> 0; inc(result,deltaRes); end; inc(divi,2); end; //if last factor of n is prime IF n <> 1 then result := result*2;
end;
var
T0 : Int64; i,next,DivCnt: Uint32;
begin
writeln('The first ',MAX,' anti-primes plus are:'); T0:= GetTickCount64; i := 1; next := 1; repeat DivCnt := getDividersCnt(i); IF DivCnt= next then Begin write(i,' '); inc(next); //if next is prime then only prime( => mostly 2 )^(next-1) is solution IF (next > 4) AND (getDividersCnt(next) = 2) then i := 1 shl (next-1) -1;// i is incremented afterwards end; inc(i); until Next > MAX; writeln; writeln(GetTickCount64-T0,' ms');
end.</lang>
- Output:
The first 32 anti-primes plus are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624 4632 65536 65572 262144 262192 263169 269312 4194304 4194306 4477456 4493312 4498641 4498752 268435456 268437200 1073741824 1073741830 525 ms
Perl
<lang perl>use strict; use warnings; use ntheory 'divisors';
print "First 15 terms of OEIS: A069654\n"; my $m = 0; for my $n (1..15) {
my $l = $m; while (++$l) { print("$l "), $m = $l, last if $n == divisors($l); }
}</lang>
- Output:
First 15 terms of OEIS: A069654 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
Phix
Uses the optimisation trick from pascal, of n:=power(2,next-1) when next is a prime>4. <lang Phix>constant limit = 15 sequence res = repeat(0,limit) integer next = 1 atom n = 1 while next<=limit do
integer k = length(factors(n,1)) if k=next then res[k] = n next += 1 if next>4 and is_prime(next) then n := power(2,next-1)-1 -- (-1 for +=1 next) end if end if n += 1
end while printf(1,"The first %d terms are: %v\n",{limit,res})</lang>
- Output:
The first 15 terms are: {1,2,4,6,16,18,64,66,100,112,1024,1035,4096,4288,4624}
Python
<lang Python> def divisors(n):
divs = [1] for ii in range(2, int(n ** 0.5) + 3): if n % ii == 0: divs.append(ii) divs.append(int(n / ii)) divs.append(n) return list(set(divs))
def sequence(max_n=None):
previous = 0 n = 0 while True: n += 1 ii = previous if max_n is not None: if n > max_n: break while True: ii += 1 if len(divisors(ii)) == n: yield ii previous = ii break
if __name__ == '__main__':
for item in sequence(15): print(item)
</lang> Output: <lang Python> 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624 </lang>
Raku
(formerly Perl 6)
<lang perl6>sub div-count (\x) {
return 2 if x.is-prime; +flat (1 .. x.sqrt.floor).map: -> \d { unless x % d { my \y = x div d; y == d ?? y !! (y, d) } }
}
my $limit = 15;
my $m = 1; put "First $limit terms of OEIS:A069654"; put (1..$limit).map: -> $n { my $ = $m = first { $n == .&div-count }, $m..Inf }; </lang>
- Output:
First 15 terms of OEIS:A069654 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624
REXX
Programming note: this Rosetta Code task (for 15 sequence numbers) doesn't require any optimization, but the code was optimized for listing higher numbers.
The method used is to find the number of proper divisors (up to the integer square root of X), and add one.
Optimization was included when examining even or odd index numbers (determine how much to increment the do loop). <lang rexx>/*REXX program finds and displays N numbers of the "anti─primes plus" sequence. */ parse arg N . /*obtain optional argument from the CL.*/ if N== | N=="," then N= 15 /*Not specified? Then use the default.*/ idx= 1 /*the maximum number of divisors so far*/ say '──index── ──anti─prime plus──' /*display a title for the numbers shown*/
- = 0 /*the count of anti─primes found " " */
do i=1 until #==N /*step through possible numbers by twos*/ d= #divs(i); if d\==idx then iterate /*get # divisors; Is too small? Skip.*/ #= # + 1; idx= idx + 1 /*found an anti─prime #; set new minD.*/ say center(#, 8) right(i, 15) /*display the index and the anti─prime.*/ end /*i*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/
- divs: procedure; parse arg x 1 y /*X and Y: both set from 1st argument.*/
if x<7 then do /*handle special cases for numbers < 7.*/ if x<3 then return x /* " " " " one and two.*/ if x<5 then return x - 1 /* " " " " three & four*/ if x==5 then return 2 /* " " " " five. */ if x==6 then return 4 /* " " " " six. */ end odd= x // 2 /*check if X is odd or not. */ if odd then #= 1; /*Odd? Assume Pdivisors count of 1.*/ else do; #= 3; y= x % 2 /*Even? " " " " 3.*/ end /* [↑] Even, so add 2 known divisors.*/ /* [↓] start with known number of Pdivs*/ do k=3 for x%2-3 by 1+odd while k<y /*for odd numbers, skip over the evens.*/ if x//k==0 then do /*if no remainder, then found a divisor*/ #= # + 2; y= x % k /*bump the # Pdivs; calculate limit Y.*/ if k>=y then do; #= # - 1; leave end /* [↑] has the limit been reached? */ end /* ___ */ else if k*k>x then leave /*only divide up to the √ x */ end /*k*/ /* [↑] this form of DO loop is faster.*/ return # + 1 /*bump "proper divisors" to "divisors".*/</lang>
- output when using the default input:
──index── ──anti─prime plus── 1 1 2 2 3 4 4 6 5 16 6 18 7 64 8 66 9 100 10 112 11 1024 12 1035 13 4096 14 4288 15 4624
Ring
<lang ring>
- Project : ANti-primes
see "working..." + nl see "wait for done..." + nl + nl see "the first 15 Anti-primes Plus are:" + nl + nl num = 1 n = 0 result = list(15) while num < 16
n = n + 1 div = factors(n) if div = num result[num] = n num = num + 1 ok
end see "[" for n = 1 to len(result)
if n < len(result) see string(result[n]) + "," else see string(result[n]) + "]" + nl + nl ok
next see "done..." + nl
func factors(an)
ansum = 2 if an < 2 return(1) ok for nr = 2 to an/2 if an%nr = 0 ansum = ansum+1 ok next return ansum
</lang>
- Output:
working... wait for done... the first 15 Anti-primes Plus are: [1,2,4,6,16,18,64,66,100,112,1024,1035,4096,4288,4624] done...
Ruby
<lang ruby>require 'prime'
def num_divisors(n)
n.prime_division.inject(1){|prod, (_p,n)| prod *= (n + 1) }
end
seq = Enumerator.new do |y|
cur = 0 (1..).each do |i| if num_divisors(i) == cur + 1 then y << i cur += 1 end end
end
p seq.take(15) </lang>
- Output:
[1, 2, 4, 6, 16, 18, 64, 66, 100, 112, 1024, 1035, 4096, 4288, 4624]
Sidef
<lang ruby>func n_divisors(n, from=1) {
from..Inf -> first_by { .sigma0 == n }
}
with (1) { |from|
say 15.of { from = n_divisors(_+1, from) }
}</lang>
- Output:
[1, 2, 4, 6, 16, 18, 64, 66, 100, 112, 1024, 1035, 4096, 4288, 4624]
Swift
Includes an optimization borrowed from the Pascal example above. <lang swift>// 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 % 2 == 0 { total += 1 n /= 2 } // 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 = 32 var n = 1 var next = 1 while next <= limit {
if next == divisorCount(number: n) { print(n, terminator: " ") next += 1 if next > 4 && divisorCount(number: next) == 2 { n = 1 << (next - 1) - 1; } } n += 1
} print()</lang>
- Output:
1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624 4632 65536 65572 262144 262192 263169 269312 4194304 4194306 4477456 4493312 4498641 4498752 268435456 268437200 1073741824 1073741830
Wren
<lang ecmascript>import "/math" for Int
var limit = 24 var res = List.filled(limit, 0) var next = 1 var n = 1 while (next <= limit) {
var k = Int.divisors(n).count if (k == next) { res[k-1] = n next = next + 1 if (next > 4 && Int.isPrime(next)) n = 2.pow(next-1) - 1 } n = n + 1
} System.print("The first %(limit) terms are:") System.print(res)</lang>
- Output:
The first 24 terms are: [1, 2, 4, 6, 16, 18, 64, 66, 100, 112, 1024, 1035, 4096, 4288, 4624, 4632, 65536, 65572, 262144, 262192, 263169, 269312, 4194304, 4194306]
zkl
<lang zkl>fcn countDivisors(n)
{ [1..(n).toFloat().sqrt()] .reduce('wrap(s,i){ s + (if(0==n%i) 1 + (i!=n/i)) },0) }</lang>
<lang zkl>n:=15; println("The first %d anti-primes plus are:".fmt(n)); (1).walker(*).tweak(
fcn(n,rn){ if(rn.value==countDivisors(n)){ rn.inc(); n } else Void.Skip }.fp1(Ref(1)))
.walk(n).concat(" ").println();</lang>
- Output:
The first 15 anti-primes plus are: 1 2 4 6 16 18 64 66 100 112 1024 1035 4096 4288 4624