Dziwna liczba to liczba, w której suma właściwych dzielników jest większa niż sama liczba i żaden podzbiór właściwych dzielników nie sumuje się do tej liczby.

Przykłady:

70 jest liczbą dziwną, ponieważ jej właściwe dzielniki (1, 2, 5, 7, 10, 14 i 35) sumują się do 74, która jest większa niż 70, a brak kombinacji tych liczb wynosi 70.

18 nie jest liczbą dziwną, ponieważ jej właściwe dzielniki (1, 2, 3, 4, 6, 9) sumują się do 25, czyli więcej niż 18, ale 3, 6 i 9 sumują się do 18.

Twoim zadaniem jest napisanie najkrótszego programu, który wprowadza przez standardowe wejście dowolną liczbę n i oblicza i drukuje do pliku lub wyznacza pierwsze n dziwnych liczb z separacją nowego wiersza. Żadne kodowanie odpowiedzi na stałe nie jest dozwolone (przepraszam, że nie określiłem tego na początku).

Aby uzyskać więcej przykładów, zobacz tę stronę: http://mathworld.wolfram.com/WeirdNumber.html

Mathematica 99 94 87

Spacje nie są potrzebne. Powolny!:

j = i = 0;
While[j<#, i++; If[Union@Sign[Tr /@ Subsets@Most@Divisors@i-i]=={-1, 1}, j++; Print@i]]&

Kosztem kilku znaków jest to szybsza wersja, która sprawdza tylko liczby parzyste i pomija wielokrotności 6, które nigdy nie są dziwne:

j = i = 0;
While[j < #, 
      i += 2; If[Mod[i, 6] != 0 && Union@Sign[Tr /@ Subsets@Most@Divisors@i - i] == {-1, 1}, 
                 j++; Print@i]] &@3

wciąż jest zbyt wolny, by mógł się przydać. Znajduje pierwsze dwa w ciągu kilku sekund, ale staje się coraz wolniejszy wraz ze wzrostem liczby dzielników.

Haskell - 129

Jestem pewien, że jest tu wiele do golfa, ale ponieważ konkurencja wydaje się na razie niska, wrzucę to.

Nie próbuj jednak tego uruchamiać, udało mi się poczekać tylko na dwa pierwsze elementy, trzeci zacznie zabierać minuty.

(%)=filter
w n=take n$e%[1..]
e x=let d=((==0).mod x)%[1..x-1]in sum d>x&&all((/=x).sum)(i d)
i[]=[[]]
i(y:z)=map(y:)(i z)++(i z)

Python 2.7 (255 bajtów)

import itertools as t
a=int(raw_input())
n=1
while a>0:
    d=[i for i in range(1,n/2+1) if not n%i]
    if all([n not in map(sum,t.combinations(d,i)) for i in range(len(d))]+[sum(d)>n]):
        print n
        a-=1
    n+=1

PHP, 267 bajtów

$n=$x=0;while($n<$argv[1]){$x++;for($i=1,$s=0,$d=array();$i<$x;$i++){if($x%$i){continue;}$s+=$i;$d[]=$i;}if($s<$x){continue;}$t=pow(2,$m=count($d));for($i=0;$i<$t;$i++){for($j=0,$s=0;$j<$m;$j++){if(pow(2,$j)&$i){$s+=$d[$j];}}if($s==$x){continue 2;}}$n++;print"$x\n";}

A oto oryginalny kod źródłowy:

$n = 0;
$x = 0;

while ($n < $argv[1]) {
    $x++;

    for ($i = 1, $sum = 0, $divisors = array(); $i < $x; $i++) {
        if ($x % $i) {
            continue;
        }

        $sum += $i;
        $divisors[] = $i;
    }

    if ($sum < $x) {
        continue;
    }

    $num = count($divisors);
    $total = pow(2, $num);

    for ($i = 0; $i < $total; $i++) {  
        for ($j = 0, $sum = 0; $j < $num; $j++) { 
            if (pow(2, $j) & $i) {
                $sum += $divisors[$j];
            }
        }

        if ($sum == $x) {
            continue 2;
        }
    }

    print "$x\n";
}

Zauważysz, że wyprowadzenie liczb zajmuje trochę czasu, ponieważ wykonuje weryfikację siłową (jednak powinieneś dostać się do 70 dość szybko).

R, 164

r=0;x=1;n=scan();while(r<n){i=which(!x%%(2:x-1));if(sum(i)-1&&!any(unlist(lapply(2:sum(i|T),function(o)colSums(combn(i,o))==x)))&sum(i)>x){r=r+1;cat(x,"\n")};x=x+1}

Wersja bez gry w golfa:

r = 0
x = 1
n = scan()
while(r < n) {
  i = which(!x %% (2:x - 1))
  if( sum(i) - 1 &&
       !any(unlist(lapply(2:sum(i | T),
                          function(o) colSums(combn(i, o)) == x))) &
       sum(i) > x
     ){ r = r + 1
        cat(x, "\n")
  }
  x = x + 1
}

To zajmuje trochę czasu z powodu brutalnej siły.

Rubin - 152

x=2;gets.to_i.times{x+=1 while((a=(1..x/2).find_all{|y|x%y==0}).reduce(:+)<=x||(1..a.size).any?{|b|a.combination(b).any?{|c|c.reduce(:+)==x}});p x;x+=1}

Ruby z ActiveSupport - 138

x=2;gets.to_i.times{x+=1 while((a=(1..x/2).find_all{|y|x%y==0}).sum<=x||(1..a.size).any?{|b|a.combination(b).any?{|c|c.sum==x}});p x;x+=1}

Naprawdę powoli i jestem prawie pewien, że jest jeszcze miejsce na grę w golfa ...

Smalltalk, 143

((1to:(Integer readFrom:Stdin))reject:[:n||d|d:=(1to:n//2)select:[:d|(n\\d)=0].d sum<n or:[(PowerSet for:d)contains:[:s|s sum=n]]])map:#printCR

Wejście:

1000

wynik:

70
836

SageMath: 143 131 bajtów

x=1
def w():
 l=x.divisors()
 return 2*x>=sum(l)or max(2*x==sum(i)for i in subsets(l))
while n:
 while w():x+=1
 print x;n-=1;x+=1

Co więcej, nawet nie gra w golfa, w kodzie i tak nie ma za dużo golfa. Najważniejsze jest to, że powinieneś najpierw wykonać test 2*x>=sum(l), dzięki czemu zaoszczędziłbyś dużo czasu obliczeniowego. Trzeba zdać sobie sprawę z tego, że maxna booleanach jest ordruga rzecz, która w(x)dotyczy Falseliczb dziwnych i liczb Trueinnych niż dziwne. Wersja bez golfa:

def w(x) :
 Divisors = x.divisors()
 return 2*x >= sum(Divisors) or max ( sum(SubS) == 2*x for SubS in subsets(Divisors) )

x=1

for k in xrange(n) :
 while w(x) : x += 1
 print x
 x += 1

C ++ - 458

To nie jest całe moje rozwiązanie, ponieważ musiałem poprosić SO o pomoc w obliczeniu sumy podzbiorów, ale wszystko inne jest moje:

#include<iostream>
#include<vector>
using namespace std;
#define v vector<int>
#define r return
#define c const_iterator
v x(int i){v d;for(int k=1;k<i;k++)if(i%k==0)d.push_back(k);r d;}bool u(v::c i,v::c e,int s){if(s==0)r 0;if(i==e)r 1;r u(i+1,e,s-*i)&u(i+1,e,s);}bool t(v&d,int i){bool b=u(d.begin(),d.end(),i);if(b)cout<<i<<endl;r b;}int main(){v d;int n;cin>>n;for(int i=2,j=0;j<n;i++){d=x(i);int l=0;for(int k=0;k<d.size();k++)l+=d[k];if(l>i)if(t(d,i))j++;}}

Długa wersja:

#include<iostream>
#include<vector>
using namespace std;

vector<int> divisors(int i) {

    vector<int> divs;
    for(int k = 1; k < i; k++)
        if(i%k==0)
            divs.push_back(k);
    return divs;
}

bool u(vector<int>::const_iterator vi, vector<int>::const_iterator end, int s) {

    if(s == 0) return 0;
    if(vi == end) return 1;
    return u(vi + 1, end, s - *vi) & u(vi + 1, end, s);
}

bool t(vector<int>&d, int i) {

    bool b = u(d.begin(), d.end(), i);
    if(b) cout<< i << endl;
    return b;
}

int main() {

    vector<int> divs;
    int n;
    cin>>n;

    for(int i = 2, j = 0; j < n; i++) {
        divs = divisors(i);

        int sum_divs = 0;
        for(int k = 0; k < divs.size(); k++)
            sum_divs += divs[k];

        if(sum_divs > i)
            if(t(divs, i))
                j++;
    }
}

Obecnie obliczył tylko pierwsze dwa (70 i 836). Potem to zabiłem.

Perl, 173

Pozwól mi dodać kolejne bezużyteczne rozwiązanie. To rozwiązanie jest tak wolne, że nie może nawet wypisać niczego poza pierwszą dziwną liczbą. Śmiem twierdzić, że jest to najwolniejsze ze wszystkich rozwiązań tutaj.

$n=<>;$i=2;while($n){$b=qr/^(?=(.+)\1{2}$)((.+)(?=.*(?(2)(?=\2$)\3.+$|(?=\1$)\3.+$))(?=.*(?=\1$)\3+$))+/;$_='x'x3x$i;if(/$b/&&($+[0]>$i)&&!/$b\1{2}$/){print"$i\n";$n--}$i++}

Próbny

Ten sam kod napisany w Javie (z którym czuję się bardziej komfortowo) nie może nawet rozpoznać drugiej dziwnej liczby (836), a już podałem numer bezpośrednio metodzie sprawdzania (zamiast zapętlania i sprawdzania każdej liczby).

Rdzeń tego rozwiązania leży w wyrażeniu regularnym:

^(?=(.+)\1{2}$)((.+)(?=.*(?(2)(?=\2$)\3.+$|(?=\1$)\3.+$))(?=.*(?=\1$)\3+$))+

I jak łańcuch jest ustawiony na 3-krotność liczby, którą sprawdzamy.

Długość łańcucha jest ustawiona na 3-krotność liczby, którą sprawdzamy i: pierwsze 2 isłuży do dopasowania sumy czynników, a ostatnia 1 ijest zarezerwowana do sprawdzenia, czy liczba jest współczynnikiem i.

(?=(.+)\1{2}$) służy do przechwytywania liczby, którą sprawdzamy.

((.+)(?=.*(?(2)(?=\2$)\3.+$|(?=\1$)\3.+$))(?=.*(?=\1$)\3+$))+dopasowuje współczynniki liczby. Późniejsza iteracja będzie pasować do mniejszego współczynnika niż wcześniejsza iteracja.

• Widzimy, że te 2 części (.+)i (?=.*(?=\1$)\3+$)wybiera razem czynnik Number sprawdzane.
• (?=.*(?(2)(?=\2$)\3.+$|(?=\1$)\3.+$)) upewnia się, że wybrany współczynnik jest mniejszy niż liczba sprawdzana w pierwszej iteracji i jest mniejszy niż poprzedni współczynnik w kolejnych iteracjach.

Wyrażenie regularne próbuje dopasować jak najwięcej czynników liczby w zakresie 2 i. Ale nie dbamy o rzeczywistą wartość sumy dzielników, dbamy tylko o to, czy liczba jest duża.

Następnie 2. wyrażenie regularne, które jest pierwszym wyrażeniem regularnym z \1{2}$dodanym. W wyniku tego wyrażenie regularne upewnia się, że suma (niektórych) czynników sprawdzanej liczby jest równa samej liczbie:

^(?=(.+)\1{2}$)((.+)(?=.*(?(2)(?=\2$)\3.+$|(?=\1$)\3.+$))(?=.*(?=\1$)\3+$))+\1{2}$

Dodane ograniczenie spowoduje, że silnik regex przeprowadzi wyszukiwanie wstecznego wszystkich możliwych podzbiorów czynników, więc będzie on bardzo wolny.

Perl, 176 174 bajtów

$n=<>;$i=9;X:while($n){@d=grep{!($i%$_)}1..$i-1;$l=0;map{$a=$_;$s=0;$s+=$d[$_]for grep{2**$_&$a}0..@d-1;$i++,next X if$s==$i;$l=1 if$s>$i}0..2**@d-1;$n--,print$i,$/if$l;$i++}

Liczba dziwnych liczb jest oczekiwana w STDIN, a znalezione liczby są drukowane do STDOUT.

Wersja bez golfa

#!/usr/bin/env perl
use strict;
$^W=1;

# read number from STDIN
my $n=<>;
# $i is the loop variable that is tested for weirdness
my $i=9; # better start point is 70, the smallest weird number
# $n is the count of numbers to find
X: while ($n) {
    # find divisors and put them in array @divisors
    my @divisors = grep{ !($i % $_) } 1 .. $i-1; # better: 1 .. int sqrt $i
    # $large remembers, if we have found a divisor sum greater than the number
    my $large = 0;
    # looping through all subsets. The subset of divisors is encoded as
    # bit mask for the divisors array.
    map {
        my $subset = $_;
        # calculate the sum for the current subset of divisors
        my $sum = 0;
        map { $sum += $divisors[$_] }
            grep { 2**$_ & $subset }
                0 .. @divisors-1;
        # try next number, if the current number is pseudoperfect
        $i++, next X if $sum == $i; # better: $i+=2 to skip even numbers
        $large = 1 if $sum > $i;
    } 0 .. 2**@divisors - 1;
    # print weird number, if we have found one
    $n--, print "$i\n" if $large;
    $i++; # better: $i+=2 to skip even numbers
}
__END__

Ograniczenia

• Powolna, brutalna siła.
• Liczba dzielników dla liczby jest ograniczona do „bitowości” liczb całkowitych w Perlu.