use strict; use warnings; use feature 'say'; use File::Map qw/map_anonymous unmap/; use PDL; # based on the caching demonstration by iM71 # https://stackoverflow.com/a/55361008 # https://stackoverflow.com/questions/38114205/c-collatz-conjecture-optimization sub collatz_longest_pdl { my ( \$size ) = @_; my ( \$length, \$number ) = ( 0, 0 ); my ( \$n, \$steps, \$tmp, \$n2 ); my \$cache = zeros( short(), \$size + 1 ); for my \$current ( 2 .. \$size ) { \$n = \$current, \$steps = 0; # count using the T(x) notation \$n % 2 ? ( \$steps += 2, \$n = (3 * \$n + 1) >> 1 ) : ( \$steps += 1, \$n = \$n >> 1 ) while \$n != 1 && \$n >= \$current; \$tmp = \$steps + at( \$cache, \$n ); set( \$cache, \$current, \$tmp ); \$length = \$tmp, \$number = \$current if \$tmp > \$length; } return ( \$number, \$length ); } sub collatz_longest_array { my ( \$size ) = @_; my ( \$length, \$number ) = ( 0, 0 ); my ( \$n, \$steps, \$tmp ); my @cache; for my \$current ( 2 .. \$size ) { \$n = \$current, \$steps = 0; # count using the T(x) notation \$n % 2 ? ( \$steps += 2, \$n = (3 * \$n + 1) >> 1 ) : ( \$steps += 1, \$n = \$n >> 1 ) while \$n != 1 && \$n >= \$current; \$tmp = \$steps + ( \$cache[ \$n ] // 0 ); \$cache[ \$current ] = \$tmp; \$length = \$tmp, \$number = \$current if \$tmp > \$length; } return ( \$number, \$length ); } sub collatz_longest_filemap { my ( \$size ) = @_; my ( \$length, \$number ) = ( 0, 0 ); my ( \$n, \$steps, \$tmp ); map_anonymous my \$cache, \$size * 2 + 2, 'shared'; # fill cache with zero's substr(\$cache, 0, \$size * 2 + 2, pack('s', 0) x ( \$size + 1 )); for my \$current ( 2 .. \$size ) { \$n = \$current, \$steps = 0; # count using the T(x) notation \$n % 2 ? ( \$steps += 2, \$n = (3 * \$n + 1) >> 1 ) : ( \$steps += 1, \$n = \$n >> 1 ) while \$n != 1 && \$n >= \$current; \$tmp = \$steps + unpack('s', substr(\$cache, \$n * 2, 2)); substr(\$cache, \$current * 2, 2, pack('s', \$tmp)); \$length = \$tmp, \$number = \$current if \$tmp > \$length; } unmap \$cache; return ( \$number, \$length ); } sub collatz_longest_scalar { my ( \$size ) = @_; my ( \$length, \$number ) = ( 0, 0 ); my ( \$n, \$steps, \$tmp ); # fill cache with zero's my \$cache = pack('s', 0) x ( \$size + 1 ); for my \$current ( 2 .. \$size ) { \$n = \$current, \$steps = 0; # count using the T(x) notation \$n % 2 ? ( \$steps += 2, \$n = (3 * \$n + 1) >> 1 ) : ( \$steps += 1, \$n = \$n >> 1 ) while \$n != 1 && \$n >= \$current; \$tmp = \$steps + unpack('s', substr(\$cache, \$n * 2, 2)); substr(\$cache, \$current * 2, 2, pack('s', \$tmp)); \$length = \$tmp, \$number = \$current if \$tmp > \$length; } return ( \$number, \$length ); } #*collatz = \&collatz_longest_pdl; # choose collatz here #*collatz = \&collatz_longest_array; #*collatz = \&collatz_longest_filemap; *collatz = \&collatz_longest_scalar; my ( \$number, \$length ) = collatz( shift || '1e7' ); say "Longest Collatz (index and value)"; say "\$number \$length";