Untouchable numbers: Difference between revisions

Note that under Windows (and possibly under Linux), Algol 68G requires that the heap size be increased in order to allow arrays big enough to handle 100 000 and 1 000 000 untouchable numbers. See [[ALGOL_68_Genie#Using_a_Large_Heap]].

{{libheader|ALGOL 68-primes}}

# proper divisors of any +ve integer #

INT max untouchable = 1 000 000;

# show the counts of untouchable numbers #

show untouchable statistics

{{out}}

<pre>

This solution implements [[Talk:Untouchable_numbers#Nice_recursive_solution]]

===The Function===

// Untouchable Numbers : Nigel Galloway - March 4th., 2021;

#include <functional>

}

};

===The Task===

;Less than 2000

int main(int argc, char *argv[]) {

int c{0}; auto n{uT{2000}}; for(auto g=n.nxt(0); g; g=n.nxt(*g+1)){if(c++==30){c=1; printf("\n");} printf("%4d ",*g);} printf("\n");

}

{{out}}

<pre>

</pre>

;Count less than or equal 100000

int main(int argc, char *argv[]) {

int z{100000}; auto n{uT{z}}; cout<<"untouchables below "<<z<<"->"<<n.count()<<endl;

}

{{out}}

<pre>

</pre>

;Count less than or equal 1000000

int main(int argc, char *argv[]) {

int z{1000000}; auto n{uT{z}}; cout<<"untouchables below "<<z<<"->"<<n.count()<<endl;

}

{{out}}

<pre>

</pre>

;Count less than or equal 2000000

int main(int argc, char *argv[]) {

int z{2000000}; auto n{uT{z}}; cout<<"untouchables below "<<z<<"->"<<n.count()<<endl;

}

{{out}}

<pre>

{{libheader| System.SysUtils}}

{{Trans|Go}}

program Untouchable_numbers;

writeln(cu:7, ' untouchable numbers were found <= ', cl);

readln;

=={{header|F_Sharp|F#}}==

This task uses [[Extensible_prime_generator#The_functions|Extensible Prime Generator (F#)]].<br>

It implements [[Talk:Untouchable_numbers#Nice_recursive_solution]]

// Applied dendrology. Nigel Galloway: February 15., 2021

let uT a=let N,G=Array.create(a+1) true, [|yield! primes64()|>Seq.takeWhile((>)(int64 a))|]

|_->N.[0]<-false; N

fL (fG 1L 0L 0) [fN 1L 0L 1]

===The Task===

;Less than 2000

uT 2000|>Array.mapi(fun n g->(n,g))|>Array.filter(fun(_,n)->n)|>Array.chunkBySize 30|>Array.iter(fun n->n|>Array.iter(fst>>printf "%5d");printfn "")

{{out}}

<pre>

</pre>

;Count less than or equal 100000

printfn "%d" (uT 100000|>Array.filter id|>Array.length)

{{out}}

<pre>

</pre>

;Count less than or equal 1000000

printfn "%d" (uT 1000000|>Array.filter id|>Array.length)

{{out}}

<pre>

</pre>

;Count less than or equal 2000000

printfn "%d" (uT 2000000|>Array.filter id|>Array.length)

{{out}}

<pre>

</pre>

;Count less than or equal 3000000

printfn "%d" (uT 3000000|>Array.filter id|>Array.length)

{{out}}

<pre>

=={{header|Go}}==

This was originally based on the Wren example but has been modified somewhat to find untouchable numbers up to 1 million rather than 100,000 in a reasonable time. On my machine, the former (with a sieve factor of 63) took 31 minutes 9 seconds and the latter (with a sieve factor of 14) took 6.2 seconds.

import "fmt"

cl := commatize(limit)

fmt.Printf("%7s untouchable numbers were found <= %s\n", cu, cl)

{{out}}

=={{header|J}}==

factor=: 3 : 0 NB. explicit

'primes powers'=. __&q: y

candidates=: 5 , [: +: [: #\@i. >.@-: NB. within considered range, all but one candidate are even.

spds=:([:sum_of_proper_divisors"0(#\@i.-.i.&.:(p:inv))@*:)f. NB. remove primes which contribute 1

We may revisit to correct the larger untouchable tallies. The straightforward algorithm presented is a little bit efficient, and, I claim, the verb <tt>(candidates-.spds)</tt> produces the full list of untouchable numbers up to its argument. It considers the sum of proper divisors through the argument squared, less primes. Since J is an algorithm description language, it may be "fairer" to state in J that "more resources required" than in some other language. [https://www.eecg.utoronto.ca/~jzhu/csc326/readings/iverson.pdf]

but the 512,000,000 sieved below is just from doubling 1,000,000 and running the sieve until we get 150232 for the number

of untouchables under 1,000,000.

function properfactorsum(n)

println("The count of untouchable numbers ≤ $N is: ", count(x -> untouchables[x], 1:N))

end

<pre>

The untouchable numbers ≤ 2000 are:

=={{header|Mathematica}}/{{header|Wolfram Language}}==

limit = 10^5;

c = Not /@ PrimeQ[Range[limit]];

Count[untouchable, _?(LessEqualThan[1000])]

Count[untouchable, _?(LessEqualThan[10000])]

{{out}}

<pre>2 246 342 540 714 804 964 1102 1212 1316 1420 1596 1774 1884

=={{header|Nim}}==

I borrowed some ideas from Go version, but keep the limit to 100_000 as in Wren version.

const

if lim == Lim1:

# Emit last message.

{{out}}

Appended a list of count of untouchable numbers out of math.dartmouth.edu/~carlp/uupaper3.pdf<BR>

Nigel is still right, that this procedure is not the way to get proven results.

program UntouchableNumbers;

{$IFDEF FPC}

OutCounts(pUntouch);

{{out}}

<pre>

=={{header|Perl}}==

{{libheader|ntheory}}

use warnings;

use enum qw(False True);

printf($fmt, scalar @untouchable, $limit) and last if $limit == ($p *= 10)

}

{{out}}

<pre>Number of untouchable numbers ≤ 2000 : 196

=={{header|Phix}}==

<span style="color: #008080;">constant</span> <span style="color: #000000;">limz</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span><span style="color: #000000;">64</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- found by experiment</span>

<span style="color: #000000;">untouchable</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2000</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">-(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()==</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">))</span>

{{out}}

<pre>

Borrow the proper divisors routine from [https://rosettacode.org/wiki/Proper_divisors#Raku here].

{{trans|Wren}}

sub propdiv (\x) {

}

}

{{out}}

<pre>

This version of REXX would need a 64-bit version to calculate the number of untouchable numbers for one million.

parse arg n cols tens over . /*obtain optional arguments from the CL*/

if n='' | n=="," then n=2000 /*Not specified? Then use the default.*/

end /*m*/ /* [↑] process an even integer. ___*/

if q.m==j then return s + m /*Was J a square? If so, add √ J */

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

{{libheader|Wren-fmt}}

Not an easy task as, even allowing for the prime tests, it's difficult to know how far you need to sieve to get the right answers. The parameters here were found by trial and error.

import "/seq" for Lst

import "/fmt" for Fmt

}

}

{{out}}