$| = 1; use bigint; sub gcd { my ($u, $v) = @_; while ($v) { ($u, $v) = ($v, $u % $v); } return abs($u); } my %known = (1=>1); my %seen = (1=>1); sub a { my $n = shift; if (not exists $known{$n}) { my $a = 1; while (1) { if (not exists $seen{$a}) { my %newseen = %seen; my %newknown = %known; my $good = 1; foreach my $p (keys %known) { if (gcd($n, $p)==1) { my $z = $a * $known{$p}; if ($z==$n*$p) { $good = 0; last; } if (not exists $newseen{$z}) { $newseen{$z} = 1; $newknown{$n * $p} = $z; } else { $good = 0; last; } } } if ($good) { %seen = %newseen; %known = %newknown; last; } } $a++; } } return $known{$n}; } foreach my $n (1..10_000) { print $n, " ", a($n), "\n"; }