Weird numbers: Difference between revisions
(Added Go) |
|||
Line 18: | Line 18: | ||
:* [[Proper_divisors|RosettaCode: Proper divisors]] |
:* [[Proper_divisors|RosettaCode: Proper divisors]] |
||
=={{header|Go}}== |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"sort" |
|||
) |
|||
func divisors(n int) []int { |
|||
divs := []int{1} |
|||
for i := 2; i*i <= n; i++ { |
|||
if n%i == 0 { |
|||
j := n / i |
|||
if i == j { |
|||
divs = append(divs, i) |
|||
} else { |
|||
divs = append(divs, i, j) |
|||
} |
|||
} |
|||
} |
|||
return divs |
|||
} |
|||
func abundant(n int, divs []int) bool { |
|||
sum := 0 |
|||
for _, div := range divs { |
|||
sum += div |
|||
} |
|||
return sum > n |
|||
} |
|||
func semiperfect(n int, divs []int) bool { |
|||
sort.Ints(divs) |
|||
le := len(divs) |
|||
ss := make([][]bool, le+1) |
|||
for i := 0; i <= le; i++ { |
|||
ss[i] = make([]bool, n+1) |
|||
ss[i][0] = true |
|||
} |
|||
for i := 1; i <= le; i++ { |
|||
for j := 1; j <= n; j++ { |
|||
if j < divs[i-1] { |
|||
ss[i][j] = ss[i-1][j] |
|||
} else { |
|||
ss[i][j] = ss[i-1][j] || ss[i-1][j-divs[i-1]] |
|||
} |
|||
} |
|||
} |
|||
return ss[le][n] |
|||
} |
|||
func main() { |
|||
count := 0 |
|||
const max = 25 |
|||
fmt.Println("The first 25 weird numbers are:") |
|||
for n := 2; count < max; n += 2 { |
|||
divs := divisors(n) |
|||
if abundant(n, divs) && !semiperfect(n, divs) { |
|||
fmt.Printf("%d ", n) |
|||
count++ |
|||
} |
|||
} |
|||
fmt.Println() |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
The first 25 weird numbers are: |
|||
70 836 4030 5830 7192 7912 9272 10430 10570 10792 10990 11410 11690 12110 12530 12670 13370 13510 13790 13930 14770 15610 15890 16030 16310 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Line 53: | Line 124: | ||
70 836 4030 5830 7192 7912 9272 10430 10570 10792 10990 11410 11690 12110 12530 12670 13370 13510 13790 13930 14770 15610 15890 16030 16310 |
70 836 4030 5830 7192 7912 9272 10430 10570 10792 10990 11410 11690 12110 12530 12670 13370 13510 13790 13930 14770 15610 15890 16030 16310 |
||
</pre> |
</pre> |
||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
Revision as of 08:56, 17 March 2019
In number theory, a weird number is a natural number that is abundant but not semiperfect.
In other words, the sum of the proper divisors (divisors including 1 but not itself) of the number is greater than the number, but no subset of those divisors sums to the number itself.
E.G. 12 is not a weird number. It is abundant; the proper divisors 1, 2, 3, 4 & 6 sum to 16, but it is semiperfect, 6 + 4 + 2 == 12.
70 is a weird number. It is abundant; the proper divisors 1, 2, 5, 7, 10, 14 & 35 sum to 74, but there is no subset of proper divisors that sum to 70.
- Task
Find and display, here on this page, the first 25 weird numbers.
- See also
Go
<lang go>package main
import (
"fmt" "sort"
)
func divisors(n int) []int {
divs := []int{1} for i := 2; i*i <= n; i++ { if n%i == 0 { j := n / i if i == j { divs = append(divs, i) } else { divs = append(divs, i, j) } } } return divs
}
func abundant(n int, divs []int) bool {
sum := 0 for _, div := range divs { sum += div } return sum > n
}
func semiperfect(n int, divs []int) bool {
sort.Ints(divs) le := len(divs) ss := make([][]bool, le+1) for i := 0; i <= le; i++ { ss[i] = make([]bool, n+1) ss[i][0] = true } for i := 1; i <= le; i++ { for j := 1; j <= n; j++ { if j < divs[i-1] { ss[i][j] = ss[i-1][j] } else { ss[i][j] = ss[i-1][j] || ss[i-1][j-divs[i-1]] } } } return ss[le][n]
}
func main() {
count := 0 const max = 25 fmt.Println("The first 25 weird numbers are:") for n := 2; count < max; n += 2 { divs := divisors(n) if abundant(n, divs) && !semiperfect(n, divs) { fmt.Printf("%d ", n) count++ } } fmt.Println()
}</lang>
- Output:
The first 25 weird numbers are: 70 836 4030 5830 7192 7912 9272 10430 10570 10792 10990 11410 11690 12110 12530 12670 13370 13510 13790 13930 14770 15610 15890 16030 16310
Julia
<lang Julia>using Primes, Combinatorics
function isweird(n)
if n < 70 return false else f = [one(n)] for (p, x) in factor(n) f = reduce(vcat, [f*p^i for i in 1:x], init=f) end pop!(f) return sum(f) > n && all(x -> sum(x) != n, powerset(f)) end
end
function testweird(N)
println("The first $N weird numbers are: ") count, n = 0, 69 while count < N if isweird(n) count += 1 print("$n ") end n += 1 end
end
testweird(25)
</lang>
- Output:
The first 25 weird numbers are: 70 836 4030 5830 7192 7912 9272 10430 10570 10792 10990 11410 11690 12110 12530 12670 13370 13510 13790 13930 14770 15610 15890 16030 16310
Perl 6
<lang perl6>sub abundant (\x) {
my @l = x.is-prime ?? 1 !! flat 1, (2 .. x.sqrt.floor).map: -> \d { my \y = x div d; next if y * d !== x; d !== y ?? (d, y) !! d }; (my $s = @l.sum) > x ?? ($s, |@l.sort(-*)) !! ();
}
my @weird = (2, 4, {|($_ + 4, $_ + 6)} ... *).map: -> $n {
my ($sum, @div) = $n.&abundant; next unless $sum; # Weird number must be abundant, skip it if it isn't. next if $sum / $n > 1.1; # There aren't any weird numbers with a sum:number ratio greater than 1.08 or so. if $n >= 10430 and ($n %% 70) and ($n div 70).is-prime { # It's weird. All numbers of the form 70 * (a prime 149 or larger) are weird } else { my $next; my $l = @div.shift; ++$next and last if $_.sum == $n - $l for @div.combinations; next if $next; } $n
}
put "The first 25 weird numbers:\n", @weird[^25];</lang>
- Output:
The first 25 weird numbers: 70 836 4030 5830 7192 7912 9272 10430 10570 10792 10990 11410 11690 12110 12530 12670 13370 13510 13790 13930 14770 15610 15890 16030 16310