/
hcn_divisible_by_2^n.pl
69 lines (52 loc) · 1.68 KB
/
hcn_divisible_by_2^n.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
#!/usr/bin/perl
# Daniel "Trizen" Șuteu
# Date: 02 July 2019
# https://github.com/trizen
# Find highly composite numbers H(n) divisible by 2^k, for k={1,2,3,...}
# Known values of n:
# 2, 3, 6, 8, 21, 23, 50, 105, 143, 221, 634, 770, 1197, 2996, 5489, 7129, 18673, 25236, 46246, 96437, 179480, 298091, 425614
# See also:
# https://oeis.org/A072847
use 5.020;
use strict;
use warnings;
use Math::GMPz;
use ntheory qw(:all);
use IO::Uncompress::Bunzip2;
use experimental qw(signatures declared_refs);
local $| = 1;
prime_precalc(1e7);
sub primorial_inflation ($n) {
state %primorial;
my $tmp = Math::GMPz->new(1);
my $prod = Math::GMPz->new(1);
foreach my \@pp(factor_exp($n)) {
my ($p, $e) = @pp;
my $prim = $primorial{$p} //= do {
my $z = Math::GMPz::Rmpz_init_nobless();
Math::GMPz::Rmpz_primorial_ui($z, $p);
$z;
};
if ($e > 1) {
Math::GMPz::Rmpz_pow_ui($tmp, $prim, $e);
Math::GMPz::Rmpz_mul($prod, $prod, $tmp);
}
else {
Math::GMPz::Rmpz_mul($prod, $prod, $prim);
}
}
return $prod;
}
# "HCN.bz2" was generated by Achim Flammenkamp, and is available at:
# http://wwwhomes.uni-bielefeld.de/achim/HCN.bz2
# "HCN_primorial_deflated.txt.bz2" is a primorial deflation of each highly composite number H(n) from "HCN.bz2", such that A108951(A181815(H(n))) = H(n).
my $z = IO::Uncompress::Bunzip2->new("HCN_primorial_deflated.txt.bz2");
my $n = 1;
while (defined(my $line = $z->getline())) {
chomp($line);
my $hcn = primorial_inflation($line);
if (Math::GMPz::Rmpz_scan1($hcn, 0) == $n) {
print $., ", ";
++$n;
}
}