M

#### Marc Girod

I bought not long ago a deck of cards with mathematical puzzles

(question on the face, answer on the back) by Martin Gardner.

One puzzle dealt with the issue of /persistence/ in the mathematical

sense.

Take an integer (decimal representation).

Take the product of the digits its representation is made of.

This gets you a new, smaller, number.

Recurse until the representation takes a single digit.

The persistence is the number of steps it took.

Unclear? Sorry I gave the deck to a friend.

But 0 is the first number of persistence 0.

10 is the first of p(1).

25 is the first of p(2).

39 is the first of p(3).

77 is the first of p(4).

Martin Gardner's question was: what is the first number of p(5)?

After some time of failing to get an answer by just thinking, I wrote

a perl script: p1

-8<----------------------

#!/usr/bin/perl -w

use strict;

use vars qw($ver);

sub prod {

my @d = @_;

my $p = 1;

$p = $p * $_ for @d;

return $p;

}

sub pers {

my ($s, $i) = @_;

if ($i) {

push @{$i}, $s;

} else {

$i = [];

print " $s: " if $ver;

}

my @d = $s =~ /(\d)/g;

if (@d > 1) {

my $p = prod @d;

return pers($p, $i);

}

print scalar @{$i}, ' (', join(' ', @{$i}), ")\n" if $ver;

return scalar @{$i};

}

my ($i, $n, $p) = (1, 1, 0);

while ($i < 10000000) {

$p = pers($i);

if ($p == $n) {

$ver = 1;

pers($i);

$ver = 0;

$n++;

}

$i++;

}

-8<-----------------

It gave me the result, but also a timing (on my laptop, looking

for 10 millions integers, and getting the first result of p(8)):

real 5m41.736s

user 5m40.175s

sys 0m0.108s

I thought that it was pretty lousy, and could be optimized, by

caching the already done calculations.

This brought in the question dealt with in a recent thread, of the

efficiency of hashes.

Trying to limit the size of the hash I use, I came up with the

following p2:

-8<-----------------------

#!/usr/bin/perl -w

use strict;

use vars qw($ver %c $h);

sub prod {

my @d = @_;

my $p = 1;

$p = $p * $_ for @d;

return $p;

}

sub pers {

my ($s, $i) = @_;

print " $s: " if $ver and !$i;

my @d = $s =~ /(\d)/g;

if (@d > 1) {

@d = sort @d;

if ($d[0]) {

shift @d while @d and $d[0] == 1;

if (@d) {

my $k = join '', @d;

if ($c{$k}) {

if (defined $i) { push @{$i}, @{$c{$k}} } else { $i = $c{$k} }

my $r = scalar @{$i};

print " $r", ' (', join(' ', @{$i}), ")\n" if $ver;

$h++;

return $r;

}

my $p = prod @d;

return pers($p, []) unless defined $i;

push @{$i}, $s;

my $r = pers($p, $i);

$c{$k} = $i;

return $r;

} else {

if (defined $i) {push @{$i}, $s} else { $i = [] }

return pers(1, $i);

}

} else {

if (defined $i) {push @{$i}, $s} else { $i = [] }

return pers(0, $i);

}

}

if (defined $i) {push @{$i}, $s} else { $i = [] }

my $r = scalar @{$i};

print " $r", ' (', join(' ', @{$i}), ")\n" if $ver;

return $r;

}

my ($i, $n, $p) = (1, 1, 0);

# $ver = 1;

while ($i < 10000000) {

$p = pers($i);

if ($p == $n) {

$ver = 1;

pers($i);

$ver = 0;

$n++;

}

$i++;

}

print "#keys: ", scalar keys %c, "\nHits: $h\n";

-8<----------------

The point is I was disappointed with the result:

real 4m32.386s

user 4m30.334s

sys 0m0.124s

Especially because 1 billion trials takes more time than 10 times 100

millions.

The numbers are larger, of course...

But, how can one do better?

The word 'persistence' makes it a bit awkward to search Google...

This script also gets soon into the 32 bit limit. Getting beyond is a

new challenge.

My resulting hash (for 10 millions) is not huge, and it was used:

#keys: 324

Hits: 1916050

Marc