Weird numbers: Difference between revisions
SqrtNegInf (talk | contribs) (Added Perl example) |
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: note use of 'ntheory') |
||
Line 127: | Line 127: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Perl 6}} |
{{trans|Perl 6}} |
||
{{libheader|ntheory}} |
|||
<lang perl>use strict; |
<lang perl>use strict; |
||
use feature 'say'; |
use feature 'say'; |
Revision as of 15:12, 23 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
<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