Weird numbers
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
<lang perl>use strict; use feature 'say';
use List::Util 'sum'; use POSIX 'floor'; use Algorithm::Combinatorics 'subsets'; use ntheory <is_prime divisors>;
sub abundant {
my($x) = @_;
my $s = sum( my @l = is_prime($x) ? 1 : grep { $x != $_ } divisors($x) );
$s > $x ? ($s, sort { $b <=> $a } @l) : ();
}
my(@weird,$n); while () {
$n++; my ($sum, @div) = abundant($n); 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 (! int $n%70) and is_prime(int $n/70)) {
# It's weird. All numbers of the form 70 * (a prime 149 or larger) are weird
} else {
my $next;
my $l = shift @div;
my $iter = subsets(\@div);
while (my $s = $iter->next) {
++$next and last if sum(@$s) == $n - $l;
}
next if $next;
}
push @weird, $n;
last if @weird == 25;
}
say "The first 25 weird numbers:\n" . join ' ', @weird;</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
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