-
Notifications
You must be signed in to change notification settings - Fork 0
/
hamming_numbers.pl
96 lines (70 loc) · 1.71 KB
/
hamming_numbers.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#!/usr/bin/perl
# Generate the generalized Hamming numbers bellow a certain limit, given a set of primes.
use 5.020;
use warnings;
use Math::GMPz;
use experimental qw(signatures);
use ntheory qw(divisors vecsum primes divisor_sum valuation);
sub check_valuation($n, $p) {
if ($p == 2) {
return (valuation($n, 2) < 15);
}
if ($p == 3) {
return ($n % ($p*$p*$p*$p*$p*$p) != 0);
}
if ($p == 5) {
return ($n % ($p*$p*$p) != 0);
}
($n % ($p*$p)) != 0;
}
sub hamming_numbers ($limit, $primes) {
my @h = (1);
foreach my $p (@$primes) {
say "Prime: $p";
foreach my $n (@h) {
if ($n * $p <= $limit and check_valuation($n, $p)) {
push @h, $n * $p;
}
}
}
return \@h;
}
# s(n) = my(d = divisors(n), s = vecsum(d) - d[#d]); forstep(i = #d-1, 1, -1, if(s <= 2*n, return(s == 2*n)); s-=d[i]); 0 \\ David A. Corneth, Feb 11 2019
sub isok {
my ($n) = @_;
$n = Math::GMPz->new($n);
if (divisor_sum($n) < 2*$n) {
return 0;
}
my @d = divisors($n);
my $s = vecsum(@d) - pop(@d);
while (@d) {
if ($s <= 2*$n) {
return $s == 2*$n;
}
$s -= pop(@d);
}
return 0;
}
my $h = hamming_numbers(10**15, primes(73));
say "Found: ", scalar(@$h), " terms";
foreach my $n(@$h) {
if (isok($n)) {
say $n;
}
#foreach my $k(0..30) {
# my $t = ($n * 2**$k);
# if (isok($t)) {
# say $t;
# }
#}
}
__END__
foreach my $n(1..1e7) {
if (isok($n)) {
say $n;
}
}
# Example: 5-smooth numbers bellow 100
#my $h = hamming_numbers(100, [2, 3, 5]);
#say join(', ', sort { $a <=> $b } @$h);