이 사람이 만든 Ulam numbers라는 정수 수열이 있는데, 두 개의 정수(일반적으로 1,2)를 시작으로 한다. 피보나치 수열이 단순히 앞의 두 수를 더해서 다음 값을 결정하는 것에 비해 Ulam numbers는 조금 더 복잡하다.
Ulam number는 두 개의 Ulam number의 합이 되는데, 대신 정확히 한 쌍의 Ulam numbers의 합한 결과여야 하며 숫자의 중복 사용은 허가되지 않는다. 예를 들어 설명하는 것이 가장 빠르겠다.
{1, 2}가 시작 숫자였다. 1+2 = 3. 3은 Ulam number이다.
{1, 2, 3}이 얻어졌다. 1 + 3 = 4. 4도 Ulam number이다. 2 + 2 = 4이지만 중복 사용은 안 된다.
{1, 2, 3, 4}가 얻어졌다. 1 + 4 = 5 이지만 2 + 3 = 5 이기 때문에 5는 Ulam number가 아니다.
이렇게 계속 구해나가면 수열이 만들어지며 이것이 바로 Ulam numbers이다.
Ulam numbers를 구하는 perl script를 작성해보았다.
use strict;
my @seq = ulam(seed => [1, 2], max => 100);
print "@seq\n";
sub ulam()
{
my %args = @_;
my @ulam = @{$args{seed}};
my $max = $args{max};
my ($i, $j) = (0, 1);
my @dups;
while(1)
{
my $s = $ulam[$i] + $ulam[$j];
push @ulam, $s;
if($i + 1 == $j)
{
$j++; $i = 0;
my (@dup, %seen);
foreach (@ulam) { push @dup, $_ if $seen{$_}++ } # find duplications
push @dups, @dup; # save duplications
foreach (@dups) { $seen{$_}++ } # update the duplication record
my @dup_removed;
foreach (@ulam) { push @dup_removed, $_ if $seen{$_} == 1 } # remove duplications
@ulam = sort {$a <=> $b} @dup_removed;
last if($ulam[$j] > $max);
}
else
{
$i++;
}
}
$#ulam = $j - 1;
return @ulam;
}
100까지의 Ulam numbers를 구하는 코드인데, 결과는 다음과 같다.
1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69 72 77 82 87 97 99위키피디아에 보여지는 것과 동일한 결과를 얻을 수 있었다.
ps.
프로그램에 주석이 없어 추가 설명을 간략히 적어둔다.
i와 j는 두 수를 더하기 위한 인덱스이다. (0, 1) (0, 2) (1, 2) (0, 3) (1, 3) (2, 3) (0, 4) ... 와 같이 진행된다. 항상 i가 j보다 작으며 i가 j보다 1작은 수가 되면 j가 하나 증가하면서 i는 0가 된다.
Ulam number는 내부 숫자의 합이므로 일단 더해서 배열에 저장해둔다.
j가 증가되기 바로 전 시점에 중복으로 나타나는 값을 점검하고 제거한다.
중복 출현한 숫자는 모두 기억하고 있어야 한다. 여러 번 계산 결과로 출현할 수 있기 때문이다.
ps2.
코드를 이쁘게 보여줄 수 있는 방법이 있으면 좋으련만.
