Problem49 - みずぴー日記

30分プログラム、その323。Problem49 - Project Euler。

項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ。

(i)3つの項はそれぞれ素数である。

(ii)各桁は他の項の置換で表される。

1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが、4桁の増加列にはもう1つ存在する。
それではこの数列の3つの項を連結した12桁の数を求めよ。

とりあえず、4桁の素数を全部求めて、その中から等差数列になっていて、置換で表現できる組み合せを探している。
置換で表現できる、をうまく書けなかったので、文字単位で分割してソートしてまた結合した上で比較している。もうちょっと賢い書き方がありそうなものだけれども。

my $as = join '',sort split //,$a;
my $bs = join '',sort split //,$b;
my $cs = join '',sort split //,$c;
if($as == $bs && $bs == $cs){
  ...

あと、Perlで配列の比較ができないのが信じられない。

使い方

$ perl problem49.pl
Deep recursion on subroutine "main::sieve" at problem49.pl line 22.
1487 4817 8147
2969 6299 9629

ソースコード

#! /usr/bin/perl
# -*- mode:perl; coding:utf-8 -*-
#
# problem49.pl -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/06/17 23:20:43
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#
use strict;
use warnings;
use Data::Dumper;

sub sieve(@){
    my ($x,@xs) = @_;
    if(@xs){
	my @ys = &sieve(grep { $_ % $x != 0} @xs);
	($x,@ys);
    }else{
	();
    }
}

my %primes = map { ($_,1)} grep {$_ >= 1_000 } sieve(2..10_000);

for my $a (sort keys %primes){
    for my $c (sort keys %primes){
	next if($a >= $c);

	my $b = ($a+$c)/2;
	if(defined $primes{$b}){
	    my $as = join '',sort split //,$a;
	    my $bs = join '',sort split //,$b;
	    my $cs = join '',sort split //,$c;
	    if($as == $bs && $bs == $cs){
		print "$a $b $c\n";
	    }
	}
    }
}

参考

過去の30分プログラム