Untouchable numbers: Difference between revisions
(→{{header|REXX}}: changed wording in the post-output section notes.) |
(→{{header|REXX}}: changed the code to be more idiomatic, optimized the sigmaP function (aliquot function) for about a 5% improvement in speed, updated (correct) count of untouchable numbers for up to and including a million.) |
||
| Line 366: | Line 366: | ||
<br>that consumed the most CPU time. |
<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).*/ |
<lang rexx>/*REXX pgm finds N untouchable numbers (numbers that can't be equal to any aliquot sum).*/ |
||
parse arg n cols tens . |
parse arg n cols tens over . /*obtain optional arguments from the CL*/ |
||
if n='' | n=="," then n=2000 /*Not specified? Then use the default.*/ |
if n='' | n=="," then n=2000 /*Not specified? Then use the default.*/ |
||
if cols='' | cols=="," | cols==0 then cols= 10 /* " " " " " " */ |
if cols='' | cols=="," | cols==0 then cols= 10 /* " " " " " " */ |
||
if tens='' | tens=="," then tens= 0 /* " " " " " " */ |
if tens='' | tens=="," then tens= 0 /* " " " " " " */ |
||
| ⚫ | |||
tell= n>0; n= abs(n) /*N>0? Then display the untouchable #s*/ |
tell= n>0; n= abs(n) /*N>0? Then display the untouchable #s*/ |
||
call genP n * |
call genP n * over /*call routine to generate some primes.*/ |
||
u.= 0 /*define all possible aliquot sums ≡ 0.*/ |
u.= 0 /*define all possible aliquot sums ≡ 0.*/ |
||
do p=1 for #; _= @.p + 1; u._= 1 /*any prime+1 is not an untouchable.*/ |
do p=1 for #; _= @.p + 1; u._= 1 /*any prime+1 is not an untouchable.*/ |
||
| Line 378: | Line 379: | ||
u.5= 0 /*special case as prime 2 + 3 sum to 5.*/ |
u.5= 0 /*special case as prime 2 + 3 sum to 5.*/ |
||
do j=2 for lim; if !.j then iterate /*Is J a prime? Yes, then skip it. */ |
do j=2 for lim; if !.j then iterate /*Is J a prime? Yes, then skip it. */ |
||
y= sigmaP() /*compute: aliquot sum (sigma P) of J.*/ |
|||
y= |
if y<=n then u.y= 1 /*mark Y as a touchable if in range. */ |
||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
end /*j*/ |
end /*j*/ |
||
call show /*maybe show untouchable #s and a count*/ |
call show /*maybe show untouchable #s and a count*/ |
||
| Line 398: | Line 393: | ||
genP: #= 9; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17; @.8=19; @.9=23 /*a list*/ |
genP: #= 9; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17; @.8=19; @.9=23 /*a list*/ |
||
!.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1; !.19=1 !.23=1 /*primes*/ |
!.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1; !.19=1 !.23=1 /*primes*/ |
||
parse arg lim; call genSq |
parse arg lim; call genSq /*define the (high) limit for searching*/ |
||
qq.10= 100 /*define square of the 10th prime index*/ |
|||
do j=@.#+6 by 2 to lim /*find odd primes from here on forward.*/ |
do j=@.#+6 by 2 to lim /*find odd primes from here on forward.*/ |
||
parse var j '' -1 _; if _==5 then iterate; if j// 3==0 then iterate |
parse var j '' -1 _; if _==5 then iterate; if j// 3==0 then iterate |
||
if j// 7==0 then iterate; if j//11==0 then iterate; if j//13==0 then iterate |
if j// 7==0 then iterate; if j//11==0 then iterate; if j//13==0 then iterate |
||
if j//17==0 then iterate; if j//19==0 then iterate; if j//23==0 then iterate |
if j//17==0 then iterate; if j//19==0 then iterate; if j//23==0 then iterate |
||
/*start dividing by the tenth prime: 29*/ |
|||
do k=10 while qq.k <= j /* [↓] divide J by known odd primes.*/ |
|||
if j//@.k==0 then iterate j /*J ÷ by a prime? Then ¬prime. ___ */ |
|||
end /*k*/ /* [↑] only process numbers ≤ √ J */ |
|||
#= #+1; @.#= j /*bump prime count; assign a new prime.*/ |
|||
!.j= 1; qq.#= j*j /*mark prime; compute square of prime.*/ |
|||
end /*j*/; return /*#: is the number of primes generated*/ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
show: w=7; $= right(2, w+1) right(5, w) /*start the list of an even prime and 5*/ |
show: w=7; $= right(2, w+1) right(5, w) /*start the list of an even prime and 5*/ |
||
| Line 416: | Line 413: | ||
end /*t*/ |
end /*t*/ |
||
if tell & $\=='' then say $ /*display a residual grid line, if any.*/ |
if tell & $\=='' then say $ /*display a residual grid line, if any.*/ |
||
if tell then say /* |
if tell then say /*show a spacing blank line for output.*/ |
||
if n>0 then say right( commas(cnt), 20) , |
if n>0 then say right( commas(cnt), 20) , /*indent the output a bit.*/ |
||
' untouchable numbers were found ≤ ' commas(n); return |
' untouchable numbers were found ≤ ' commas(n); return |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
sigmaP: s= 1 /*set initial sigma sum (S) to 1. ___*/ |
|||
if j//2 then do m=3 by 2 while q.m<j /*divide by odd integers up to the √ J */ |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
if j//m==0 then s=s+m+j%m /*add the two divisors to the sum. */ |
|||
end /*m*/ /* [↑] process an even integer. ___*/ |
|||
| ⚫ | |||
| ⚫ | |||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
| Line 452: | Line 459: | ||
1,212 untouchable numbers were found ≤ 10,000 |
1,212 untouchable numbers were found ≤ 10,000 |
||
13,863 untouchable numbers were found ≤ 100,000 |
13,863 untouchable numbers were found ≤ 100,000 |
||
150, |
150,252 untouchable numbers were found ≤ 1,000,000 |
||
</pre> |
</pre> |
||
Due to complications of choosing an overreach limit of eighteen, I cannot be sure to any certainty that the count is correct for one million (using an overreach factor of eighteen). |
|||
I am currently re-running the REXX program using an overreach limit of twenty. |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
Revision as of 21:18, 11 February 2021
- Definitions
-
- Untouchable numbers are also known as nonaliquot numbers.
- An untouchable number is a positive integer that cannot be expressed as the sum of all the proper divisors of any positive integer. (From Wikipedia)
- The sum of all the proper divisors is also known as the aliquot sum.
- An untouchable are those numbers that are not in the image of the aliquot sum function. (From Wikipedia)
- Untouchable numbers: impossible values for the sum of all aliquot parts function. (From OEIS: The On-line Encyclopedia of Integer Sequences®)
- An untouchable number is a positive integer that is not the sum of the proper divisors of any number. (From MathWorld™)
- Observations and conjectures
All untouchable numbers > 5 are composite numbers.
No untouchable number is perfect.
No untouchable number is sociable.
No untouchable number is a Mersenne prime.
No untouchable number is one more than a prime number, since if p is prime, then the sum of the proper divisors of p2 is p + 1.
No untouchable number is three more than an odd prime number, since if p is an odd prime, then the sum of the proper divisors of 2p is p + 3.
The number 5 is believed to be the only odd untouchable number, but this has not been proven: it would follow from a slightly stronger version of the Goldbach's conjecture, since the sum of the proper divisors of pq (with p, q being distinct primes) is 1 + p + q.
There are infinitely many untouchable numbers, a fact that was proven by Paul Erdős.
According to Chen & Zhao, their natural density is at least d > 0.06.
- Task
-
- show (in a grid format) all untouchable numbers ≤ 2,000.
- show (for the above) the count of untouchable numbers.
- show the count of untouchable numbers from unity up to (inclusive):
- 10
- 100
- 1,000
- 10,000
- 100,000
- ... or as high as is you think is practical.
- all output is to be shown here, on this page.
- See also
-
- Wolfram MathWorld: untouchable number.
- OEIS: A005114 untouchable numbers.
- OEIS: a list of all untouchable numbers below 100,000 (inclusive).
- Wikipedia: untouchable number.
- Wikipedia: Goldbach's conjecture.
Go
... but now goes up to 1,000,000 as I'm reasonably sure (see talk page) that the figure obtained is correct. <lang go>package main
import "fmt"
func sumDivisors(n int) int {
sum := 0
i := 1
k := 2
if n%2 == 0 {
k = 1
}
for i*i <= n {
if n%i == 0 {
sum += i
j := n / i
if j != i {
sum += j
}
}
i += k
}
return sum - n
}
func sieve(n int) []bool {
n++
s := make([]bool, n*4) // all false by default
for i := 0; i <= n; i++ {
s[sumDivisors(i)] = true
}
return s
}
func isPrime(n int) bool {
if n < 2 {
return false
}
if n%2 == 0 {
return n == 2
}
if n%3 == 0 {
return n == 3
}
d := 5
for d*d <= n {
if n%d == 0 {
return false
}
d += 2
if n%d == 0 {
return false
}
d += 4
}
return true
}
func commatize(n int) string {
s := fmt.Sprintf("%d", n)
if n < 0 {
s = s[1:]
}
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
if n >= 0 {
return s
}
return "-" + s
}
func main() {
limit := 1000000
s := sieve(20 * limit)
untouchable := []int{2, 5}
for n := 6; n <= limit; n += 2 {
if !s[n] && !isPrime(n-1) && !isPrime(n-3) {
untouchable = append(untouchable, n)
}
}
fmt.Println("List of untouchable numbers <= 2,000:")
count := 0
for i := 0; untouchable[i] <= 2000; i++ {
fmt.Printf("%6s", commatize(untouchable[i]))
if (i+1)%10 == 0 {
fmt.Println()
}
count++
}
fmt.Printf("\n\n%7s untouchable numbers were found <= 2,000\n", commatize(count))
p := 10
count = 0
for _, n := range untouchable {
count++
if n > p {
cc := commatize(count - 1)
cp := commatize(p)
fmt.Printf("%7s untouchable numbers were found <= %9s\n", cc, cp)
p = p * 10
if p == limit {
break
}
}
}
cu := commatize(len(untouchable))
cl := commatize(limit)
fmt.Printf("%7s untouchable numbers were found <= %s\n", cu, cl)
}</lang>
- Output:
List of untouchable numbers <= 2,000:
2 5 52 88 96 120 124 146 162 188
206 210 216 238 246 248 262 268 276 288
290 292 304 306 322 324 326 336 342 372
406 408 426 430 448 472 474 498 516 518
520 530 540 552 556 562 576 584 612 624
626 628 658 668 670 708 714 718 726 732
738 748 750 756 766 768 782 784 792 802
804 818 836 848 852 872 892 894 896 898
902 926 934 936 964 966 976 982 996 1,002
1,028 1,044 1,046 1,060 1,068 1,074 1,078 1,080 1,102 1,116
1,128 1,134 1,146 1,148 1,150 1,160 1,162 1,168 1,180 1,186
1,192 1,200 1,212 1,222 1,236 1,246 1,248 1,254 1,256 1,258
1,266 1,272 1,288 1,296 1,312 1,314 1,316 1,318 1,326 1,332
1,342 1,346 1,348 1,360 1,380 1,388 1,398 1,404 1,406 1,418
1,420 1,422 1,438 1,476 1,506 1,508 1,510 1,522 1,528 1,538
1,542 1,566 1,578 1,588 1,596 1,632 1,642 1,650 1,680 1,682
1,692 1,716 1,718 1,728 1,732 1,746 1,758 1,766 1,774 1,776
1,806 1,816 1,820 1,822 1,830 1,838 1,840 1,842 1,844 1,852
1,860 1,866 1,884 1,888 1,894 1,896 1,920 1,922 1,944 1,956
1,958 1,960 1,962 1,972 1,986 1,992
196 untouchable numbers were found <= 2,000
2 untouchable numbers were found <= 10
5 untouchable numbers were found <= 100
89 untouchable numbers were found <= 1,000
1,212 untouchable numbers were found <= 10,000
13,863 untouchable numbers were found <= 100,000
150,252 untouchable numbers were found <= 1,000,000
Julia
I can prove that the number to required to sieve to assure only untouchables for N 100,000 is less than 2,499,000,000, but the 32,000,000 sieved below is just from doubling 1,000,000 and running the sieve until we get the Wren results. <lang julia>using Primes
function properfactorsum(n)
f = [one(n)]
for (p,e) in factor(n)
f = reduce(vcat, [f*p^j for j in 1:e], init=f)
end
pop!(f)
return sum(f)
end
const maxtarget, sievelimit = 100_000, 32_000_000 const untouchables = ones(Bool, maxtarget)
for i in 2:sievelimit
n = properfactorsum(i)
if n <= maxtarget
untouchables[n] = false
end
end for i in 6:maxtarget
if untouchables[i] && (isprime(i - 1) || isprime(i - 3))
untouchables[i] = false
end
end
println("The untouchable numbers ≤ 2000 are: ") for (i, n) in enumerate(filter(x -> untouchables[x], 1:2000))
print(rpad(n, 5), i % 10 == 0 || i == 196 ? "\n" : "")
end for N in [2000, 10, 100, 1000, 10_000, 100_000]
println("The count of untouchable numbers ≤ $N is: ", count(x -> untouchables[x], 1:N))
end
</lang>
- Output:
The untouchable numbers ≤ 2000 are: 2 5 52 88 96 120 124 146 162 188 206 210 216 238 246 248 262 268 276 288 290 292 304 306 322 324 326 336 342 372 406 408 426 430 448 472 474 498 516 518 520 530 540 552 556 562 576 584 612 624 626 628 658 668 670 708 714 718 726 732 738 748 750 756 766 768 782 784 792 802 804 818 836 848 852 872 892 894 896 898 902 926 934 936 964 966 976 982 996 1002 1028 1044 1046 1060 1068 1074 1078 1080 1102 1116 1128 1134 1146 1148 1150 1160 1162 1168 1180 1186 1192 1200 1212 1222 1236 1246 1248 1254 1256 1258 1266 1272 1288 1296 1312 1314 1316 1318 1326 1332 1342 1346 1348 1360 1380 1388 1398 1404 1406 1418 1420 1422 1438 1476 1506 1508 1510 1522 1528 1538 1542 1566 1578 1588 1596 1632 1642 1650 1680 1682 1692 1716 1718 1728 1732 1746 1758 1766 1774 1776 1806 1816 1820 1822 1830 1838 1840 1842 1844 1852 1860 1866 1884 1888 1894 1896 1920 1922 1944 1956 1958 1960 1962 1972 1986 1992 The count of untouchable numbers ≤ 2000 is: 196 The count of untouchable numbers ≤ 10 is: 2 The count of untouchable numbers ≤ 100 is: 5 The count of untouchable numbers ≤ 1000 is: 89 The count of untouchable numbers ≤ 10000 is: 1212 The count of untouchable numbers ≤ 100000 is: 13863
Phix
Note: the limit of 18*n is unsound, albeit matching the above b005114.txt list, see talk page (1464) <lang Phix>procedure untouchable(integer n, cols=0, tens=0)
bool tell = n>0
n = abs(n)
sequence sums = repeat(0,n+3)
for i=1 to n do
integer p = get_prime(i)
if p>n then exit end if
sums[p+1] = 1
sums[p+3] = 1
end for
sums[5] = 0
-- for j=2 to 2*n do
for j=2 to 18*n do -- see talk page (1464)
integer y = sum(factors(j,-1))
if y<=n then
sums[y] = 1
end if
end for
if tell then
printf(1,"The list of all untouchable numbers <= %d:\n",{n})
end if
string line = " 2 5"
integer cnt = 2
for t=6 to n by 2 do
if sums[t]=0 then
cnt += 1
if tell then
line &= sprintf("%,8d",t)
if remainder(cnt,cols)=0 then
printf(1,"%s\n",line)
line = ""
end if
end if
end if
end for
if tell then
if line!="" then
printf(1,"%s\n",line)
end if
printf(1,"\n")
end if
printf(1,"%,20d untouchable numbers were found <= %,d\n",{cnt,n})
for p=1 to tens do
untouchable(-power(10,p))
end for
end procedure
untouchable(2000, 10, 5)</lang>
- Output:
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
290 292 304 306 322 324 326 336 342 372
406 408 426 430 448 472 474 498 516 518
520 530 540 552 556 562 576 584 612 624
626 628 658 668 670 708 714 718 726 732
738 748 750 756 766 768 782 784 792 802
804 818 836 848 852 872 892 894 896 898
902 926 934 936 964 966 976 982 996 1,002
1,028 1,044 1,046 1,060 1,068 1,074 1,078 1,080 1,102 1,116
1,128 1,134 1,146 1,148 1,150 1,160 1,162 1,168 1,180 1,186
1,192 1,200 1,212 1,222 1,236 1,246 1,248 1,254 1,256 1,258
1,266 1,272 1,288 1,296 1,312 1,314 1,316 1,318 1,326 1,332
1,342 1,346 1,348 1,360 1,380 1,388 1,398 1,404 1,406 1,418
1,420 1,422 1,438 1,476 1,506 1,508 1,510 1,522 1,528 1,538
1,542 1,566 1,578 1,588 1,596 1,632 1,642 1,650 1,680 1,682
1,692 1,716 1,718 1,728 1,732 1,746 1,758 1,766 1,774 1,776
1,806 1,816 1,820 1,822 1,830 1,838 1,840 1,842 1,844 1,852
1,860 1,866 1,884 1,888 1,894 1,896 1,920 1,922 1,944 1,956
1,958 1,960 1,962 1,972 1,986 1,992
196 untouchable numbers were found <= 2,000
2 untouchable numbers were found <= 10
5 untouchable numbers were found <= 100
89 untouchable numbers were found <= 1,000
1,212 untouchable numbers were found <= 10,000
13,863 untouchable numbers were found <= 100,000
REXX
Some optimization was done to the code to produce prime numbers, since a simple test could be made to exclude
the calculation of touchability for primes as the aliquot sum of a prime is unity.
This saved around 15% of the running time.
A fair amount of code was put into the generation of primes, but the computation of the aliquot sum was the area
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 over . /*obtain optional arguments from the CL*/
if n= | n=="," then n=2000 /*Not specified? Then use the default.*/
if cols= | cols=="," | cols==0 then cols= 10 /* " " " " " " */
if tens= | tens=="," then tens= 0 /* " " " " " " */
if over= | over=="," then over= 20 /* " " " " " " */
tell= n>0; n= abs(n) /*N>0? Then display the untouchable #s*/
call genP n * over /*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 prime 2 + 3 sum to 5.*/
do j=2 for lim; if !.j then iterate /*Is J a prime? Yes, then skip it. */
y= sigmaP() /*compute: aliquot sum (sigma P) of J.*/
if y<=n then u.y= 1 /*mark Y as a touchable if in range. */
end /*j*/
call show /*maybe show untouchable #s and a count*/ if tens>0 then call powers /*Any "tens" specified? Calculate 'em.*/ exit cnt /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? genSq: do _=1 until _*_>lim; q._= _*_; end; q._= _*_; _= _+1; q._= _*_; return grid: $= $ right( commas(t), w); if cnt//cols==0 then do; say $; $=; end; return powers: do pr=1 for tens; call 'UNTOUCHA' -(10**pr); end /*recurse*/; return /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: #= 9; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17; @.8=19; @.9=23 /*a list*/
!.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1; !.19=1 !.23=1 /*primes*/
parse arg lim; call genSq /*define the (high) limit for searching*/
qq.10= 100 /*define square of the 10th prime index*/
do j=@.#+6 by 2 to lim /*find odd primes from here on forward.*/
parse var j -1 _; if _==5 then iterate; if j// 3==0 then iterate
if j// 7==0 then iterate; if j//11==0 then iterate; if j//13==0 then iterate
if j//17==0 then iterate; if j//19==0 then iterate; if j//23==0 then iterate
/*start dividing by the tenth prime: 29*/
do k=10 while qq.k <= j /* [↓] divide J by known odd primes.*/
if j//@.k==0 then iterate j /*J ÷ by a prime? Then ¬prime. ___ */
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j /*bump prime count; assign a new prime.*/
!.j= 1; qq.#= j*j /*mark prime; compute square of prime.*/
end /*j*/; return /*#: is the number of primes generated*/
/*──────────────────────────────────────────────────────────────────────────────────────*/ show: w=7; $= right(2, w+1) right(5, w) /*start the list of an even prime and 5*/
cnt= 2 /*count of the only two primes in list.*/
do t=6 by 2 to n; if u.t then iterate /*Is T touchable? Then skip it. */
cnt= cnt + 1; if tell then call grid /*bump count; maybe show a grid line. */
end /*t*/
if tell & $\== then say $ /*display a residual grid line, if any.*/
if tell then say /*show a spacing blank line for output.*/
if n>0 then say right( commas(cnt), 20) , /*indent the output a bit.*/
' untouchable numbers were found ≤ ' commas(n); return
/*──────────────────────────────────────────────────────────────────────────────────────*/ sigmaP: s= 1 /*set initial sigma sum (S) to 1. ___*/
if j//2 then do m=3 by 2 while q.m<j /*divide by odd integers up to the √ J */
if j//m==0 then s=s+m+j%m /*add the two divisors to the sum. */
end /*m*/ /* [↑] process an odd integer. ___*/
else do m=2 while q.m<j /*divide by all integers up to the √ J */
if j//m==0 then s=s+m+j%m /*add the two divisors to the sum. */
end /*m*/ /* [↑] process an even integer. ___*/
if q.m==j then return s + m /*Was J a square? If so, add √ J */
return s /* No, just return. */</lang>
- output when using the default inputs:
2 5 52 88 96 120 124 146 162 188
206 210 216 238 246 248 262 268 276 288
290 292 304 306 322 324 326 336 342 372
406 408 426 430 448 472 474 498 516 518
520 530 540 552 556 562 576 584 612 624
626 628 658 668 670 708 714 718 726 732
738 748 750 756 766 768 782 784 792 802
804 818 836 848 852 872 892 894 896 898
902 926 934 936 964 966 976 982 996 1,002
1,028 1,044 1,046 1,060 1,068 1,074 1,078 1,080 1,102 1,116
1,128 1,134 1,146 1,148 1,150 1,160 1,162 1,168 1,180 1,186
1,192 1,200 1,212 1,222 1,236 1,246 1,248 1,254 1,256 1,258
1,266 1,272 1,288 1,296 1,312 1,314 1,316 1,318 1,326 1,332
1,342 1,346 1,348 1,360 1,380 1,388 1,398 1,404 1,406 1,418
1,420 1,422 1,438 1,476 1,506 1,508 1,510 1,522 1,528 1,538
1,542 1,566 1,578 1,588 1,596 1,632 1,642 1,650 1,680 1,682
1,692 1,716 1,718 1,728 1,732 1,746 1,758 1,766 1,774 1,776
1,806 1,816 1,820 1,822 1,830 1,838 1,840 1,842 1,844 1,852
1,860 1,866 1,884 1,888 1,894 1,896 1,920 1,922 1,944 1,956
1,958 1,960 1,962 1,972 1,986 1,992
196 untouchable numbers were found ≤ 2,000
- output when using the inputs: 0 , 5
2 untouchable numbers were found ≤ 10
5 untouchable numbers were found ≤ 100
89 untouchable numbers were found ≤ 1,000
1,212 untouchable numbers were found ≤ 10,000
13,863 untouchable numbers were found ≤ 100,000
150,252 untouchable numbers were found ≤ 1,000,000
Wren
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. <lang ecmascript>import "/math" for Int, Nums import "/seq" for Lst import "/fmt" for Fmt
var sieve = Fn.new { |n|
n = n + 1
var s = List.filled(n*4, false)
for (i in 0..n) {
var sum = Nums.sum(Int.properDivisors(i))
s[sum] = true
}
return s
}
var limit = 1e5 var s = sieve.call(14 * limit) var untouchable = [2, 5] var n = 6 while (n <= limit) {
if (!s[n] && !Int.isPrime(n-1) && !Int.isPrime(n-3)) untouchable.add(n) n = n + 2
}
System.print("List of untouchable numbers <= 2,000:") for (chunk in Lst.chunks(untouchable.where { |n| n <= 2000 }.toList, 10)) {
Fmt.print("$,6d", chunk)
} System.print() Fmt.print("$,6d untouchable numbers were found <= 2,000", untouchable.count { |n| n <= 2000 }) var p = 10 var count = 0 for (n in untouchable) {
count = count + 1
if (n > p) {
Fmt.print("$,6d untouchable numbers were found <= $,7d", count-1, p)
p = p * 10
if (p == limit) break
}
} Fmt.print("$,6d untouchable numbers were found <= $,d", untouchable.count, limit)</lang>
- Output:
List of untouchable numbers <= 2,000:
2 5 52 88 96 120 124 146 162 188
206 210 216 238 246 248 262 268 276 288
290 292 304 306 322 324 326 336 342 372
406 408 426 430 448 472 474 498 516 518
520 530 540 552 556 562 576 584 612 624
626 628 658 668 670 708 714 718 726 732
738 748 750 756 766 768 782 784 792 802
804 818 836 848 852 872 892 894 896 898
902 926 934 936 964 966 976 982 996 1,002
1,028 1,044 1,046 1,060 1,068 1,074 1,078 1,080 1,102 1,116
1,128 1,134 1,146 1,148 1,150 1,160 1,162 1,168 1,180 1,186
1,192 1,200 1,212 1,222 1,236 1,246 1,248 1,254 1,256 1,258
1,266 1,272 1,288 1,296 1,312 1,314 1,316 1,318 1,326 1,332
1,342 1,346 1,348 1,360 1,380 1,388 1,398 1,404 1,406 1,418
1,420 1,422 1,438 1,476 1,506 1,508 1,510 1,522 1,528 1,538
1,542 1,566 1,578 1,588 1,596 1,632 1,642 1,650 1,680 1,682
1,692 1,716 1,718 1,728 1,732 1,746 1,758 1,766 1,774 1,776
1,806 1,816 1,820 1,822 1,830 1,838 1,840 1,842 1,844 1,852
1,860 1,866 1,884 1,888 1,894 1,896 1,920 1,922 1,944 1,956
1,958 1,960 1,962 1,972 1,986 1,992
196 untouchable numbers were found <= 2,000
2 untouchable numbers were found <= 10
5 untouchable numbers were found <= 100
89 untouchable numbers were found <= 1,000
1,212 untouchable numbers were found <= 10,000
13,863 untouchable numbers were found <= 100,000