[seqfan] Re: Primes with increasing digits

[hv at crypt.org]

franktaw at netscape.net wrote:
:http://www.research.att.com/~njas/sequences/A068827
:
:This sequence is wrong. After a(10) = 8929, the next term should be 
:8969. Inserting that, the next term is 12347, but again after 89189, 
:the next term should be 89237, then 89269, 89293, 456791, 456923, and 
:we are now on a completely different trajectory.
:
:These terms were computed semi-manually (making repeated calls to 
:PARI's nextprime function), so I'm not 100% confident of them - but I 
:am sure that the terms out there now are incorrect. Any volunteers to 
:actually program the thing?
:
:Franklin T. Adams-Watters

I get these with the code below, which assumes I've actually understood
the definition correctly:

2 3 5 7 89 127 919 1237 8923 8929 8969 12347 89123 89137 89189 89237 89269
89293 89393 89459 89491 89567 89591 89597 89689 89797 89891 89897 91237 91249
123457 891239 891349 891379 891389 891391 891491 891493 891593 891679 891797
891893 891923 891929 891967 892357 892391 892457 892579 892597 892919 893479
893489 893567 893591 893797 893897 893917 893929 893939 893989 894589 894689
894791 894793 894893 894917 894923 894947 895691 895789 895913 895927 895957
896897 896927 896947 897947 898927 912349 1234789 1234967 8912347 8912357
8912359 8912389 8912459 8912489 8912591 8912689 8912791 8912927 8912929
8912989 8913497 8913589 8913689 8913791 8913893 8913917 8913923 8914567
8914679 8914897 8914937 8914957 8915897 8915917 8916913 8916923 8917891
8917913 8917927 8917949 8918927 8918929 8918939 8918947 8918989 8919139
8919149 8919167 8919191 8919259 8919293 8919347 8919349 8919389 8919497
8919593 8919689 8919893 8923457 8923469 8923591 8923679 8923891 8923897
8923913 8923969 8924579 8924893 8924917 8924969 8925691 8925793 8925797
8925913 8925967 8925979 8925989 8926891 8926927 8926937 8927927 8927957
8927959 8928929 8928979 8929127 8929139 8929169 8929189 8929289 8929367
8929391 8929567 8929597 8929897 8934589 8934791 8934917 8934923 8935691
8935793 8935919 8935957 8936791 8936797 8936947 8936969 8936989 8937893
8937917 8937919 8937947 8937949 8939159 8939167 8939179 8939197 8939257
8939347 8939369 8939393 8939591 8939597 8939789 8939891 8945939 8945947
8945969 8946797 8946893 8946919 8947891 8948917 8948939 8948957 8948969
8949167 8949379 8949469 8949679 8949791 8949797 8956789 8956891 8956897
8956939 8956949 8957917 8957957 8957989 8958947 8959147 8959157 8959169
8959367 8959369 8959789 8959891 8967913 8967919 8967947 8967967 8968913
8968937 8968957 8969179 8969189 8969237 8969293 8969347 8969393 8969479
8969579 8969689 8969789 8969791 8978923 8978969 8978989 8979137 8979149
8979169 8979259 8979293 8979359 8979379 8979479 8979497 8979569 8979797
8989139 8989237 8989259 8989369 8989459 8989469 8989493 8989567 8989579
8989691 8989697 8989789 12345923 

It would be possible to get subsequent terms much faster by noting where
the first bad pair occurs, and adjusting the point to search from
accordingly.

Hugo
--
#!/usr/bin/perl -w
use strict;
$| = 1;
use Math::Pari qw(nextprime);
my $badpair = badpairs();
my $prev = 2;
while (1) {
	my $cur = nextA086627($prev);
	print "$cur ";
	$prev = $cur;
}
exit 0;

sub nextA086627 {
	my $prev = shift;
	my $digit = substr("$prev", -1, 1);
	my $cur = $prev;
	while (1) {
		$cur = nextprime($cur + 1);
		next if "$digit$cur" =~ $badpair;
		return $cur;
	}
}

sub badpairs {
	my @bad;
	# each successive digit [...] is greater than the previous digit
	for my $first (0 .. 8) {
		for my $second (0 .. $first) {
			push @bad, "$first$second";
		}
	}
	# or if the previous digit = 9, than any digit except 0 or 9 may follow
	push @bad, "90", "99";
	return join '|', @bad;
}