Rosetta Code

Untouchable numbers: Difference between revisions

Page Discussion

Untouchable numbers (view source)

Revision as of 19:56, 9 February 2021

1,475 bytes added ,  3 years ago
m
→‎{{header|REXX}}: moved more code into subroutines for more idiomatic code, moved subroutines in alphabetical order.
m (→‎{{header|REXX}}: added the fifth power of ten to the output.)
m (→‎{{header|REXX}}: moved more code into subroutines for more idiomatic code, moved subroutines in alphabetical order.)
Line 290:
 
=={{header|REXX}}==
Some optimization was done to the code to produce prime numbers,   since a simple test could be made to exclude
<br>the calculation of touchability for primes as the aliquot sum of a prime is unity.
<br>This saved around &nbsp; '''15%''' &nbsp; of the running time.
 
A fair amount of code was put into the generation of primes, &nbsp; but the computation of the aliquot sum was the area
<br>that consumed the most CPU time.
<lang rexx>/*REXX pgm finds N untouchable numbers (numbers that can't be equal to any aliquot sum).*/
parse arg n cols tens . /*obtain optional arguments from the CL*/
Line 296 ⟶ 302:
if tens='' | tens=="," then tens= 0 /* " " " " " " */
tell= n>0; n= abs(n) /*N>0? Then display the untouchable #s*/
call genP n /*call routine to generate some primes.*/
!u.= 0 /*define all possible aliquot sums ≡ 0.*/
do p=1 for #; _= @.p + 1; !u._= 1 /*any prime+1 is not an untouchable.*/
_= @.p + 3; !u._= 1 /* " prime+3 " " " " */
end /*p*/ /* [↑] this will also rule out 5. */
!u.5= 0 /*special case as primes 2+3 sum to 5. */
lim= n*9; do j=2 for 18*if n;>=1e4 then ylim= sigma(j)lim*2 /*checkadjust allthe numberslimit for touchabilitya larger N. */
ifdo y>nj=2 thenfor iteratelim; if !.y=j 1 then iterate /*Is J a /*markprime? Y number asYes, athen touchableskip numberit. */
y= sigma(j); if y<=n then u.y= 1 /*mark Y as a touchable if in range. */
end /*j*/
exit 0 call show /*stickmaybe ashow forkuntouchable in#s it,and a we're all done. count*/▼
 
if tens==>0 then exit cnt call powers /*Any "tens" specified? No, thenCalculate exit'em.*/▼
if tell then say 'The list of all untouchable numbers ≤' n":" /*display title of the #s*/
exit cnt $= ' 2 5'; cnt= 2 /*startstick thea listfork ofin anit, even primewe're all anddone. 5*/
do t=6 by 2 to n /*traipse through the even numbers. */▼
if !.t==1 then iterate /*Is it touchable? Then skip this #. */▼
cnt= cnt + 1 /*bump the count of untouchable numbers*/▼
if \tell then iterate /*Not telling? Then skip grid build. */▼
$= $ right( commas(t), 7) /*add a number to the list; bump count.*/
if cnt//cols\==0 then iterate /*allow X untouchable numbers per line.*/▼
say $; $= /*display a line of untouchables; clear*/
end /*t*/▼
if tell & $\=='' then say $ /*display a residual line, if any. */
if tell then say
if n>0 then say right( commas(cnt), 20) ' untouchable numbers were found ≤ ' commas(n)▼
▲if tens==0 then exit cnt /*Any "tens" specified? No, then exit.*/
do p=1 for tens; z= untoucha(-(10**p) ) /*invoke this program recursively. */
end /*pow*/
▲exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?
grid: $= $ right( commas(t), w); if cnt//cols==0 then do; say $; $=; end; return
powers: do pr=1 for tens; call 'UNTOUCHA' -(10**p); end /*recurse*/; return
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17; @.8=19 /*a list of low primes*/
!.2=1; @.3=1; @.5=1; !.7=1; !.11=1; !.13=1; !.17=1; !.19=1 /*define some primes. */
sq.9= 9*9; #= 8; !.= 0; sd= 9 /*square; #primes; is_prime; start of ÷*/
do j=@.#+2 by 2 to n*18 /*find odd primes from here on forward.*/
parse var j '' -1 _ /*obtain the last decimal digit of J. */
▲ if cnt//cols\ _==05 then iterate /*allowJ divisible by 5 X? untouchable numbersThen perignore lineit.*/
▲ if !.tj// 3==10 then iterate /*Is" it touchable " " 3 ? Then skip" " this #." */
▲ if \tellj// 7==0 then iterate /*Not" " " 7 telling? Then skip" " grid build." */
▲ if sayj//11==0 $; then iterate $= /*" " " 11 /*display? " " a line of untouchables;" clear*/
if j//13==0 then iterate /*" " " 13 ? " " " */
if j//17==0 then iterate /*" " " 17 ? " " " */
if j//19==0 then iterate /*" " " 19 ? " " " */
do k=sd while sq.k<=j /* [↓] divide Y by known odd primes.*/
if j // @.k == 0 then iterate j /*J ÷ by a prime? Then ¬prime. ___ */▼
▲ do t=6 by 2 toend /*k*/ n /*traipse through[↑] the evenonly process numbers. ≤ √ J */
▲ cnt#= cnt #+ 1 /*bump the number (count) of untouchableprimes. numbers*/
!.j= 1; @.#= j; sq.#= j*j /*assign the #th prime; flag as prime.*/
end /*j*/; return /*#: is the number of primes generated*/▼
/*──────────────────────────────────────────────────────────────────────────────────────*/
genPshow: w=7; $= right(2, @.w+1=) 2; right(5, @.2= 3w); #cnt= 2 /*definestart the startlist of somean even lowprime primes.and 5*/
do jt=@.#+26 by 2 to n; if u.t then iterate /*Is T touchable? Then skip it. /*find odd primes from here on forward.*/
do kcnt=2 while k*k<=j cnt + 1; if tell then call grid /*bump [↓]count; dividemaybe byshow thea knowngrid odd primesline. */
▲ end /*t*/
▲ if j // @.k == 0 then iterate j /*J ÷ by a prime? Then ¬prime. ___ */
end /*k*/ if tell & $\=='' then say $ /*display [↑] only process numbers ≤ a √residual Jgrid line, if any.*/
#= #+1; if tell @.#= j then say /*bumpadd numbera ofspacing primes;blank line assignfor primeoutput. */
if n>0 then say right( commas(cnt), 20) ,
▲ end /*j*/; return /*#: is the number of primes generated*/
▲if n>0 then say right( commas(cnt), 20) ' untouchable numbers were found ≤ ' commas(n); return
/*──────────────────────────────────────────────────────────────────────────────────────*/
sigma: procedure; parse arg x; ododd= x // 2 /*use either EVEN or ODD integers. */
ssum= 1 /*set initial sigma sum to unity. ___*/
do jm=2+ododd by 1+ododd while jm*jm<x /*divide by all integers up to the √ x */
if x//jm==0 then ssum= ssum + jm + x%jm /*add the two divisors to the sum. */
end /*jm*/ /* [↑] % is REXX integer division. */
/* ___ */
if jm*jm==x then return ssum + j m /*Was Z a square? If so, add √ x */
return s sum /*return (sigma) sum of the divisors. */</lang>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
The list of all untouchable numbers ≤ 2000:
2 5 52 88 96 120 124 146 162 188
206 210 216 238 246 248 262 268 276 288
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/307797"