Weird numbers

Weird numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

• OEIS:A006037 Weird numbers
• RosettaCode: Abundant, deficient and perfect number classifications
• RosettaCode: Proper divisors

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

Translation of: Perl 6

Library: ntheory

<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

Python

Functional

The first 50 seem to take c. 300 ms <lang python>Weird numbers

from itertools import islice from time import time from math import sqrt

1. weirds :: Gen [Int]

def weirds():

   Generator for weird numbers.
      (Abundant, but not semi-perfect)
   x = 1
   while True:
       w = until(abNotSemi)(succ)(x)
       yield w
       x = 1 + w

1. main :: IO ()

def main():

   Test

   start = time()
   n = 50
   xs = take(n)(
       weirds()
   )

   # oneBased :: Int -> String
   def oneBased(i):
       return str(1 + i)
   print(
       tabulated('First ' + str(n) + ' weird numbers:\n')(oneBased)(str)(
           index(xs)
       )(range(0, n))
   )
   print(
       '\nApprox computation time: ' +
       str(int(1000 * (time() - start))) + ' ms'
   )

1. abNotSemi :: Int -> Bool

def abNotSemi(n):

   Predicate :: abundant and not semi-perfect ?
   ds = descPropDivs(n)
   d = sum(ds) - n
   if 1 > d:
       return False  # Not abundant.
   else:
       if d in ds:
           return False
       else:
           return not hasSum(d, ds)

1. hasSum :: Int -> [Int] -> Bool

def hasSum(n, xs):

   Does any subset of xs sum to n ?
      (Assuming xs to be sorted in descending
      order of magnitude)
   def go(n, xs):
       if xs:
           h, t = xs[0], xs[1:]
           if n < h:  # Head too big. Forget it. Tail ?
               return go(n, t)
           else:
               # The head IS the target ?
               # Or the tail contains a sum for the
               # DIFFERENCE between the head and the target ?
               # Or the tail contains some OTHER sum for the target ?
               return n == h or go(n - h, t) or go(n, t)
       else:
           return False
   return go(n, xs)

1. descPropDivs :: Int -> [Int]

def descPropDivs(n):

   Descending positive divisors of n,
      excluding n itself
   root = sqrt(n)
   intRoot = int(root)
   blnSqr = root == intRoot
   lows = [x for x in range(1, 1 + intRoot) if 0 == n % x]
   return [
       n // x for x in (
           lows[1:-1] if blnSqr else lows[1:]
       )
   ] + list(reversed(lows))

1. GENERIC -------------------------------------------------

1. compose (<<<) :: (b -> c) -> (a -> b) -> a -> c

def compose(g):

   Right to left function composition.
   return lambda f: lambda x: g(f(x))

1. index (!!) :: [a] -> Int -> a

def index(xs):

   Item at given (zero-based) index.
   return lambda n: None if 0 > n else (
       xs[n] if (
           hasattr(xs, "__getitem__")
       ) else next(islice(xs, n, None))
   )

1. succ :: Enum a => a -> a

def succ(x):

   The successor of a value. For numeric types, (1 +).
   return 1 + x if isinstance(x, int) else (
       chr(1 + ord(x))
   )

1. tabulated :: String -> (a -> String) ->
2. (b -> String) ->
3. (a -> b) -> [a] -> String

def tabulated(s):

   Heading -> x display function -> fx display function ->
               f -> value list -> tabular string.
   def go(xShow, fxShow, f, xs):
       w = max(map(compose(len)(xShow), xs))
       return s + '\n' + '\n'.join(
           xShow(x).rjust(w, ' ') + ' -> ' + fxShow(f(x)) for x in xs
       )
   return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
       xShow, fxShow, f, xs
   )

1. take :: Int -> [a] -> [a]
2. take :: Int -> String -> String

def take(n):

   The prefix of xs of length n,
      or xs itself if n > length xs.
   return lambda xs: (
       xs[0:n]
       if isinstance(xs, list)
       else list(islice(xs, n))
   )

1. until :: (a -> Bool) -> (a -> a) -> a -> a

def until(p):

   The result of repeatedly applying f until p holds.
      The initial seed value is x.
   def go(f, x):
       v = x
       while not p(v):
           v = f(v)
       return v
   return lambda f: lambda x: go(f, x)

1. MAIN ----------------------------------------------------

if __name__ == '__main__':

   main()</lang>

Output:

First 50 weird numbers:

 1 -> 70
 2 -> 836
 3 -> 4030
 4 -> 5830
 5 -> 7192
 6 -> 7912
 7 -> 9272
 8 -> 10430
 9 -> 10570
10 -> 10792
11 -> 10990
12 -> 11410
13 -> 11690
14 -> 12110
15 -> 12530
16 -> 12670
17 -> 13370
18 -> 13510
19 -> 13790
20 -> 13930
21 -> 14770
22 -> 15610
23 -> 15890
24 -> 16030
25 -> 16310
26 -> 16730
27 -> 16870
28 -> 17272
29 -> 17570
30 -> 17990
31 -> 18410
32 -> 18830
33 -> 18970
34 -> 19390
35 -> 19670
36 -> 19810
37 -> 20510
38 -> 21490
39 -> 21770
40 -> 21910
41 -> 22190
42 -> 23170
43 -> 23590
44 -> 24290
45 -> 24430
46 -> 24710
47 -> 25130
48 -> 25690
49 -> 26110
50 -> 26530

Approx computation time: 288 ms