倍数になる13進数 DouKaku?

ここにある正の整数xがあります。xは2桁以上です。この数字の並びが13進法表記であるとみなすと、10進法表記であると見なした場合の倍数になります。この条件を満たす最も小さいxを求めるプログラムを書いてください。

例えばxが567の時、これを13進法表記と見なすと5 * 13 * 13 + 6 * 13 + 7 で 930 になります。930は567の倍数ではないので、567は条件を満たしません。条件を満たす数を見つけ出すプログラムを書いてください。「条件を満たす数を出力するプログラム」ではありません。(print 567などは禁止ということ。)

stack overflowに注意

f = lambda do |i|
   j = i.to_s(10).to_i(13)
   if j % i == 0
     i
   else
     f.call i+1
   end
end

puts f.call(10) # 2-digit constraint

短く書くとこんなかんじかなぁ　ブルートフォースな感じです

1 2	for x in (x for x in xrange(1, 32767) if (int(str(x), 13) % x)==0): print x

ああ2桁以上なんですね。問題をよく読まない回答が多いなぁ＜俺

素直に1桁ずつ進数変換して割り算

#!/usr/local/bin/perl

use strict;
use warnings;

my $max = 10000;

for ( my $orig = 10; $orig <= $max; $orig++ ) {

        print ".";

        my $num13 = 0;
        my $length = 0;

        my $orig_tmp = $orig;
        while( $orig_tmp ) {
                $num13 += ( 13 ** $length ) *  ( $orig_tmp % 10 );
                $orig_tmp = int ( $orig_tmp / 10 );
                $length++;
        }

        if( $num13 % $orig == 0 ) {
                print "\nFound: $orig => $num13\n";
                exit 0;
        }
}

| x |
x := 10.
[('13r', x printString) asNumber isDivisibleBy: x] whileFalse: [x := x + 1].
^x

しかも列挙じゃなくて、最小を一個出せばいいのね

進数変換にreduceを使ってみた版

#!/usr/local/bin/perl

use strict;
use warnings;

use List::Util qw( reduce );

my $max = 10000;

for ( my $orig = 10; $orig <= $max; $orig++ ) {

        print ".";

        my $num13 = reduce { 13 * $a + $b } split //, $orig;

        if( $num13 % $orig == 0 ) {
                print "\nFound: $orig => $num13\n";
                exit 0;
        }
}

端折ってみた版

$a/$bでwarningが出るのはどうしたらよいんだろう……。

#!/usr/local/bin/perl

use strict;
use warnings;

use List::Util qw( reduce );

my $max = 10000;

for my $orig ( 10 .. $max ) {
        my $num13 = reduce { 13 * $a + $b } split //, $orig;
        print "Found: $orig => $num13\n" and exit 0
                if( $num13 % $orig == 0 );
}

仕事もしないで、高速版を作ってみました。最小の数じゃなくて、全（のはず）組み合わせを列挙します。

# -*- coding: utf-8 -*-
"""
ここにある正の整数xがあります。iは2桁以上です。この数字の並びが13進法表記であるとみなすと、10進法表記であると見なした場合の倍数になります。この条件を満たす最も小さいxを求めるプログラムを書いてください。 
"""

def match(rest, nums, modulus):
    """与えられた係数でマッチする数を出力"""
    if len(modulus)==1:
        # 一の位
        # 一の位の係数で割り切れたらOK
        div, mod = divmod(rest, modulus[0])
        if mod==0 and 0<=div<10:
            r = nums+[div]
            return [''.join(str(x) for x in r)]
        return []
    else:
        result = []

        # 可能性がなかったらやめる
        if not sum(modulus)<rest<sum(x * 9L for x in modulus):
            return result        
        
        cur, next = modulus[0], modulus[1:]
        for x in xrange(0, 10):
            r = rest - x * cur
            if r<0:
                break
            result.extend(match(r, nums+[x], next))
        return result
        

def thriteen():
    """お題な数を出力する"""
    # n倍で回す
    for n in xrange(2, 100):
        left_modulus = [] # 左辺の係数
        
        # 係数が-になるまで列挙
        for u in xrange(10):
            m = n * (10L ** u) - (13L ** u)
            if m<0:
                break
            left_modulus.append(m)

        # 右辺の係数
        right_modulus = -m
        
        left_modulus.reverse()
        # 一番高い位は1～9だろう
        for x in xrange(1, 10):
            for answer in match(x * right_modulus, [], left_modulus):
                yield str(x)+answer
        
if __name__=='__main__':
    for x in thriteen():
        print x, divmod(long(x, 13), long(x))

public class Radix {
	
	public static void main(String[] args) {
		for (int i = 10;; i++) {
			int j = Integer.parseInt(Integer.toString(i), 13);
			if (j % i == 0) {
				System.out.println(i);
				return;
			}
		}
	}
	
}

シンプルに手計算してみた。

#include <stdio.h>

//13進で換算
int calc_13(int num){
	int ret=0;
	int i;
	int dig=100000;	//多分これより小さい桁だからここまでも大丈夫。
	
	//上位桁から順番に計算
	do{
		ret*=13;
		ret+=num/dig;
		num%=dig;
		dig/=10;
	}while(dig);
	return ret;
}

int main(){
	int i;
	
	for(i=1;i<100000;i++){
		if(calc_13(i)==i*2){
			printf("13n:%d 10n:%d\n",i,i*2);
			return 0;
		}
	}
	return 0;
}

#!/usr/bin/env gosh

(define *max* 100000000)

(define (func n b)
  (let ((quo (quotient n 10)))
    (if (zero? quo) (modulo n 10)
        (+ (* (func quo b) b) (func (modulo n 10) b)))))

(define (foo x)
  (cond ((zero? (modulo (func x 13) x)) x)
        ((> x *max*) 'over)
        (else (foo (+ x 1)))))

(print (foo 10))

main :: IO ()
main = print $ head $ filter p13 [10..]

p13 :: Int -> Bool
p13 x = (0 ==) $ (`mod` x) $ foldl (+) 0 $ f x 1
    where
      f :: Int -> Int -> [Int]
      f 0 _ = []
      f x n = ((x `mod` 10) * n) : f (x `div` 10) (n * 13)

関数名に困ったけど、答えを出すのはanswerを使ってください。
(find-num 最大値 N進数) で11進数以上のもので問題と同じ事が出来ます。

(defun figure-number (number)
  (let ((result nil) (seed number))
    (loop while (< 0 seed) do
	 (multiple-value-bind (f r)(floor seed 10)
	   (push r result)
	   (setf seed f)))
    (reverse result)))

(defun 10->n (number n)
  (let ((fig-list (figure-number number)) (result 0) (i 0))
    (loop for ite in fig-list do
	 (incf result (* ite (expt n i)))
	 (incf i)
	 finally (return result))))
	 
(defun 10->n-p (number n)
  (if (equal number (gcd number (10->n number n)))
      T
      nil))

(defun find-num (max n)
  (let ((result nil))
    (loop for i from 1 to max do
	 (and (10->n-p i n)
	      (push i result))
	 finally (return (reverse result)))))

(defun answer (max)
  (find-num max 13))

; CL-USER> (answer 2000)
; (1 2 3 4 5 6 7 8 9 1557 1560 1614)

#include<stdio.h>
#include<stdlib.h>
int main(void){
  int i=9;
  char s[9];
  while(sprintf(s,"%d",++i),i+i!=strtol(s,0,13));
  puts(s);
  return 0;
}

(define (multinum)
  (define (obase-13 n)
    (string->number (number->string n) 13))
  (let loop ((n 10))
    (if (zero? (remainder (obase-13 n) n))
        n
        (loop (+ n 1)))))

(print (multinum))

間違って大文字ではじまる"G"aucheタグをつくってしまいました。
すいません。

Bash もなかなかやりおるのぉ。

print_magic_13 () {
  for ((trid=10; dec=13#${trid}, dec % trid != 0; trid++));
  do :
  done

  echo $dec "($trid in tri-decimal)"
}

難読版？

module Main (main) where
main :: IO ()
main = print $ head $ filter p [10..]
  where
    p = (0 ==) . s (mod . (r . show)) id
    r = foldl ((+) . (13*)) 0 . map (read . (:[]))
    s f g x = f x (g x)

高階関数を使ったものに変えてみた。変更箇所のみ

(defun 10-> (n)
  (lambda(number)
    (let ((fig-list (figure-number number)) (result 0) (i 0))
      (loop for ite in fig-list do
	   (incf result (* ite (expt n i)))
	   (incf i)
	 finally (return result)))))
	 
(defun 10->n-p (n)
  (lambda(number)
    (if (equal number (gcd number (funcall (10-> n) number)))
	T
	nil)))

(defun find-num (n)
  (lambda(max)
    (let ((result nil))
      (loop for i from 1 to max do
	   (and (funcall (10->n-p n) i)
		(push i result))
	   finally (return (reverse result))))))

(defun answer (max)
  (funcall (find-num 13) max))

Emacs Lisp です。C-x C-e とか M-: とか M-x ielm とかで式を評価。

(let ((n 10))
  (while (not (zerop (mod (string-to-number (number-to-string n) 13) n)))
    (setq n (+ n 1)))
  n)

while(0)だと何故か回らなかったので、trueを入れて強引に。

<?php
$x = 10;
do {
	$y = $x * 2;
	$z = base_convert($x,13,10);
	if ( "$y" == "$z" ) {
		echo "\n答えは、$x です。\n";
		break;
	}
	$x++;
} while(true);
?>

同案多数か？

public class Sample {
    public static void main(String[] args) {
        for (int x = 10; ; x++) {
            int triX = Integer.parseInt(Integer.toString(x), 13);
            if (triX == 2 * x) {
                System.out.println(x);
                break;
            }
        }
    }
}

あんまりスマートではないですが、OCamlも。

let rec f acc m = function 0->acc | x->f (acc+m*(x mod 10)) (m*13) (x/10)
let rec g n = if (f 0 1 n) mod n = 0 then n else g (n+1)

let _ = Printf.printf "%d\n" (g 10)

5行目間違ってますね。問題はちゃんと読みましょうという感じです。すみません。

何も考えずに書いてしまった...

def n_adic(str, n)
  str = str.to_s
  res, i = 0, 0
  (str.reverse.split '').each do |c|
    res += c.to_i * (n ** i)
    i += 1
  end
  res
end

def check(number, target)
  i = 1
  while(number * i <= target)
    return true if(number * i ==  target)
    i += 1
  end
end

i = 10
while true
  n10 = n_adic(i, 10)
  n13 = n_adic(i, 13)
  if(check(n10, n13))
    p "n=10:#{n10} n=13:#{n13}"
    break
  end
  i += 1
end

Haskell のリスト内包表記だと殆ど問題文そのままに書けますね。

asBaseN :: Int -> Int -> Int
asBaseN base 0 = 0
asBaseN base n = (n `mod` 10) + (base * asBaseN base (n `div` 10))

main :: IO ()
main = print $ head [x | x <- [10..], (asBaseN 13 x) `mod` x == 0]

計算の回数を減らすために上の桁から決めていく方法を考えてみた。

<?php
// 2倍から8倍まで探す。それ以上はオーバーフローする
for($n=2;$n<9;++$n)
{	echo "x$n: ";
	// 式を展開してみると解るが、一番上の桁は1になるらしい。
	// その桁を探す
	for($c=10;intval((string)$c,13)<=$n*$c;$c*=10)
		;
	$a=$c*2-1;
	if(intval((string)$a,13)-$n*$a>0)
	{	// 探しても無駄な場合
		echo "no ans.\n";
		continue;
	}
	for($a=$c;;)
	{	if(($c/=10)<1)
		{	echo "no ans.\n";
			break;
		}
		for($i=0;$i<9;++$i)
		{	$a+=$c;
			$d=intval((string)$a,13)-$n*$a;
			echo "\t$a $d\n";
			if(!$d)
			{	echo "$a\n";
				break 2;
			}
			if($d<0)
			{	$a-=$c;
				break;
			}
		}
	}
}
?>

まだ言語一覧にないけど Scala で。

import java.lang.Integer._
import scala.Iterator._
import scala.Console._

object Question14 {
  def main(args: Array[String]) = {
    val numbers = for (n <- from(10) if parseInt(n.toString, 13) % n == 0) yield n
    println(numbers.next)
  }
}

ごめんなさい。「一番上の桁1らしい」は嘘でした。
2以上も探すバージョン。

<?php
// 2倍から7倍まで探す。それ以上はオーバーフローする
for($n=2;$n<8;++$n)
{	echo "x$n: ";
	// 一番上の桁を探す
	for($c0=10;intval((string)$c0,13)<=$n*$c0;$c0*=10)
		;
	for($c1=$c0;;$c1+=$c0)
	{	$c=$c0;
		$a=$c1+$c0-1;
		if(intval((string)$a,13)-$n*$a>0)
		{	// 探しても無駄
			echo "no ans.\n";
			break;
		}
		for($a=$c1;;)
		{	if(($c/=10)<1)
			{	echo "no ans.\n";
				break;
			}
			for($i=0;$i<9;++$i)
			{	$a+=$c;
				$d=intval((string)$a,13)-$n*$a;
				echo "\t$a $d\n";
				if(!$d)
				{	// 発見
					echo "$a\n";
					break 2;
				}
				if($d<0)
				{	// 通り過ぎた
					$a-=$c;
					break;
				}
			}
		}
	}
}
?>

適当に。

1	$><<("10".."10000").find{\|x\|"#{x}".to_i(13)%x<1}

関数名は気にしちゃ負けです:D

ansで答えの10進数とその倍数（13進数の10進数表記）を返します。
barの引数に適当に基数、基数、n倍数、昇順で何番目を渡すと、うまくいけば何かが帰るかもしれません（適当。

(defun bar (a b n pos)
  (labels
      ((basea->b (a b)
         (lambda (x)
           (labels ((ex (x f acc)
                      (if (zerop x)
                          acc
                        (ex (truncate (/ x b)) (* f a) (+ acc (* (mod x b) f))))))
             (ex x 1 0)))))
    (labels
        ((happy (a b n x pos)
           (labels
               ((b->a (x)
                  (funcall (basea->b b a) x)))
             (if (= (/ (b->a x) x) n)
                 (if (zerop pos)
                     (values x (b->a x))
                   (happy a b n (1+ x) (1- pos)))
               (happy a b n (1+ x) pos)))))
      (happy a b n 1 (1- pos)))))

(defun ans ()
  (bar 10 13 2 1))

> (ans)
1557 ;
3114

F#なのはConsole.WriteLineあたりだけ

open System;;

let solv () =
    let rec trans = function
        | 0 -> 0
        | n -> (n mod 10) + (trans (n / 10)) * base
    and base = 13
    and solving m =
             if (trans m) mod m = 0
             then m
             else solving (m+1)
    in solving 10;;

Console.WriteLine( solv() );;

string->numberって基数を変えられたんですねぇ。便利だ。参考にして、ストリームを使った意欲作(笑)にしてみました。 4つ目から出力されません。

1
2
3

(use util.stream)
(define (p n) (zero? (remainder (string->number (number->string n) 13) n)))
(stream-for-each print (stream-filter p (stream-iota -1 10)))

SWI-prologでも。prologは10年ぶりです。
でも、res/1で、答えをwritelnした後、トラックバックを指示できないって、こういう仕様でしたっけ？
 % pl -qs mul.pl
1557
 %

tr10to13(N, N) :- N < 10.
tr10to13(N, R) :- N >= 10, tr10to13(N // 10, Rs), R is Rs * 13 + (N mod 10).
mul10x13(N) :- tr10to13(N, N13), 0 =:= N13 mod N.
res(N) :- mul10x13(N), writeln(N).
res(N) :- N1 is N + 1, res(N1).
:-res(10), halt.

失礼。failを忘れていました。トラックバックにて延々と答えを探し続けます。

tr10to13(N, N) :- N < 10.
tr10to13(N, R) :- N >= 10, tr10to13(N // 10, Rs), R is Rs * 13 + (N mod 10).
mul10x13(N) :- tr10to13(N, N13), 0 =:= N13 mod N.
res(N) :- mul10x13(N), writeln(N), fail.
res(N) :- N1 is N + 1, res(N1).
:-res(10), halt.

普通に。

import itertools

for x in itertools.count(10):
    if int(str(x), 13) % x == 0:
        print x
        break

トラックバック→バックトラックです。
お恥ずかしいです。（顔から火が出そう）

10000まで総当り。 (問題文の『i』ってなに)

use strict;

foreach my $x (10 .. 10000) {
    my $n13 = 0;
    $n13 = $n13 * 13 + $_ foreach (split(//, $x));
    print "$x ($n13)\n" and exit if ($n13 % $x == 0);
}

1
2
3

(do ((x 10 (1+ x)))
    ((= (mod (parse-integer (format nil "~D" x) :radix 13) x) 0)
     (print x)))

あってるハズだが、検証不能...
つか、最初に2倍から20倍の範囲で探すとか, 指数関数だから１個でいいだろうとか、
根拠レスなアドホック入っているのがイカポン. X-(

んん～、ソース読んでも何やってるかさっぱり分からん. メモをコピペしとこう.

(n-1) d0 + (10n - 13) d1 + (100n - 169) d2  + (1000n - 2197) d3  ... = 0

             (n-1) d0         d0      2 d0
+       (10n - 13) d1       7 d1     17 d1
+     (100n - 169) d2      31 d2    131 d2
+   (1000n - 2197) d3    -197 d3    803 d3
+  (10000n -28561) d4   -8561 d4   1439 d4
+(100000n -371293) d5 -171293 d5 -71293 d5

#! /usr/bin/env python

import string;

for n in range(2, 20):
    p = 0;
    a = [];
    a9s = [];
    while(True):
        ap = 10**p*n - 13**p;
        a.append(ap);
        if (ap < 0): break;
        if (len(a9s)==0):
            a9s.append(ap*9);
        else:
            a9s.append(ap*9+a9s[-1]);
        p+=1;
    if (ap + a9s[-1] > 0):
        #print a
        #print a9s
        bp=1;
        while(bp*ap + a9s[-1] > 0):
            rest = -bp*ap;
            b=[];
            b.append(bp);
            fr = range(1,len(a)-1);
            fr.reverse();
            for f1 in fr:
                bm = int((rest-a9s[f1-1])/a[f1])+1;
                if (bm > 9): break;
                b.append(bm);
                rest -= a[f1]*bm;
            if (bm > 9 or rest > 9):
                bp += 1;
                continue ;
            b.append(rest);
            ans=string.join(map(lambda(x): "%d"%(x), b), "");
            print "x%d: "%(n)+ans;
            bp += 1;

int(x,13) ってやり方があったのか、と他の方のコードを見て後悔。

# -*- coding: utf-8 -*-

for x in range(10,100000):
    y = 0
    for c in str(x):
        y = y * 13 + int(c)
    if y % x == 0:
        print x

普通ですみません＞＜

1	for(var i=13;i%i.toString(13);i++);alert(i);

皆さんやってると思いますが Excel で。

- セルに値を記入
    A1  "10進数"
    B1  1000
    C1  100
    D1  10
    E1  1
    F1  "13進数"
    G1  "余り"
    A2  10
- セルに数式を記入
    B2  =MOD(ROUNDDOWN($A2/B$1,0),10)
    C2～E2  B2 をコピー
    F2  =B2*2197+C2*169+D2*13+E2
    G2  =MOD(F2,A2)
- A2～G2 を選択し、フィルハンドル(選択領域の右下の小さい■)をドラッグし、10000行分くらい下にコピー
- オートフィルタ(Alt を押しながら D-F-F)を有効にして、G列 で「０」にフィルタ。

この解が有限個なのか無限個なのかが気になる…… とりあえず４桁の次は８桁に３つあるなあ。

for($i=10;$i<10000;$i++){
	$x=base_convert($i,13,10);
	if($x==$i*2){
		echo $i.'<br>';
		echo $x.'<br>';
		break;
	}
}

b13i :: Integer -> Integer
b13i 0 = 0
b13i x = let (d, m) = divMod x 10
         in m + 13 * b13i d

equal x = x * 2 == b13i x

main = do putStrLn $ show $ find equal [10..]

(define (_ x) 
  (if (zero? (modulo (string->number (number->string x) 13) x))
    (print x)
    (_ (+ x 1))))
(_ 10)

お題から少し外れるが、条件を満たす数を探し続けるプログラム。汚かったり最適化の余地が残っているのはご勘弁。これを２時間走らせて４６桁まで探索済み。見つかっている一番大きい値は 60065682893774087238167921857827939124689630 (44桁)。やっぱり無限にありそうだなあ。

def search(m, rem, result)
  rem2 = rem[1..rem.length-1]
  sum = rem2.inject{|a,b|a+b}
  min = (-sum*9 - m)/rem[0]
  max = (sum*9 - m)/rem[0]
  min = 0 if min < 0
  max = 9 if max > 9
  return if min > max
  min.upto(max) do |x|
    if rem2.length == 1
      if (m+x*rem[0]) % rem2[0] == 0
        y = - (m+x*rem[0]) / rem2[0]
        puts (result+[x, y]).join('') if y>=0 && y<=9
      end
    else
      search m+x*rem[0], rem2, result+[x]
    end
  end
end

d=3 # keta - 1
while
  min_n = 13**d / 10**d
  max_n = (9*(13**(d+1)-1)/12) / (10**(d+1)-1)
  min_n, max_n = max_n, min_n if min_n > max_n
  puts "keta: #{d+1}"
  1.upto(9) do |ad| # highest digit
    x13 = 13**d*ad
    x10 = 10**d*ad
    min_n.upto(max_n) do |n|
      m = x13 - x10*n
      #puts [m, n].join(',')
      rem = []
      0.upto(d-1){|i| rem.unshift 13**i - 10**i * n }
      search m, rem, [ad]
    end
  end
  d+=1
end

xの誤植でした。修正しました。

ご指摘ありがとうございます。

"import Data.List" を忘れていました…

N進数の変換ってなかったっけ

using System;
class Program
{
  static void Main()
  {
    for (int i = 0; ; ++i)
    {
      if (Convert(i, 13) % i == 0)
      {
        Console.WriteLine(i);
        return;
      }
    }
  }
  private static int Convert(int i, int b)
  {
    if (i < 0) return -Convert(-i, b);
    int res = 0, j = 1;
    while (i > 0)
    {
      res += j * (i % 10);
      i /= 10;
      j *= b;
    }
    return res;
  }
}

消しておきました。

題意は triX % x == 0 なのですけど、
実は最小の答えは(皆さんの想像通り)xの2倍なので
出てくる答えは同じなんですよね～

よくみたらダメダメじゃないかこのコード

先のコードはバグがあって、解の見落としが発生することがわかりました。すんません。ということで修正＆最適化したものを投稿。３０桁くらいまでならほぼ瞬殺で出力します。

def search(m, rem, result)
  rem2 = rem[1..rem.length-1]
  ai = -rem[0]
  min = rem2.inject(m+ai-1){|sum,a|sum+(a>0?0:a*9)}/ai
  max = rem2.inject(m){|sum,a|sum+(a>0?a*9:0)}/ai
  #puts "#{m}, #{rem.inspect}, #{min}, #{max}"
  min = 0 if min < 0
  max = 9 if max > 9
  return if min > max
  min.upto(max) do |x|
    if rem2.length == 1
      if (m-x*ai) % rem2[0] == 0
        y = (x*ai-m) / rem2[0]
        puts "#{result}#{x}#{y}" if y>=0 && y<=9
      end
    else
      search m-x*ai, rem2, "#{result}#{x}"
    end
  end
end

d=3 # keta - 1
while true
  puts "keta: #{d+1} =========================================================="
  max_n = 13**d / 10**d
  1.upto(9) do |ad| # highest digit
    x13 = ad*13**d
    x10 = ad*10**d
    min_n = (x13 + 9*(13**d-1)/12) / (x10 + (10**d-1))
    puts [min_n, max_n].join(', ') if min_n > max_n
    min_n.upto(max_n) do |n|
      m = x13 - x10*n
      rem = []
      0.upto(d-1){|i| rem.unshift 13**i - 10**i * n }
      search m, rem, "#{ad}"
    end
  end
  d+=1
end

それだと、i.toString(13)が"1a"のとき( i = 23)に、i%i.toString(13)がNaNになって、ループを抜けてしまうのではないでしょうか。

1	for(i=13;n=i.toString(13),i%n\|\|isNaN(n);i++);alert(n)

FromDigits, IntegerDigits で任意の進数で変換ができました．

n = 10;
While[FromDigits[IntegerDigits[n], 13] != n*2, n++];

Print[n];
Print[FromDigits[IntegerDigits[n], 13]];

おっしゃる通りですね。うっかりしてました＞＜

(require :iter)
(in-package :iter)
(defun radix-13 ()
  (iter (for i from 10)
        (finding i such-that
                 (let* ((str (format nil "~a" i))
                        (radix-13 (parse-integer str :radix 13)))
                   (zerop (mod radix-13 i))))))
(radix-13)                              ; => 1557

(parse-integer "1557" :radix 13)        ; => 3114
(mod 3114 1557)                         ; => 0

1
2
3

print((function f(n) {
	return parseInt(n, 13) % n ? f(++n) : n;
})(10))

以下のように起動します．
erl -noshell -s bai13 bai13 -s init stop

-module(bai13).
-export([bai13/0]).

bai13() ->
    bai13(10).

bai13(N) ->
    N2 = conv13_10(N),
    if
        N2 == N * 2 ->
            io:format("~p ~p~n", [N, N2]),
            ok;
        true ->
            bai13(N+1)
    end.

conv13_10(N) ->
    conv13_10(integer_to_list(N), 0).

conv13_10([Digit|RestDigit], Number) ->
    conv13_10(RestDigit, Number * 13 + list_to_integer([Digit]));
conv13_10([], Number) ->
    Number.

module Main (main) where


fromDecimal :: (Integral a) => a -> a -> a
fromDecimal n x = f 0 x 1
  where
    f r 0 _ = r
    f r y z = let (d,m) = y `divMod` 10
              in  f (r + m * z) d (z * n)


main :: IO ()
main = putStr $ show $ head $ filter (\x -> fromDecimal 13 x `mod` x == 0) [10..]

C++のカバレッジ稼ぎ。C++なのは出力部分だけだけど（汗）

#include <iostream>

int radix13(unsigned int n)
{
    if (n == 0)
    {
        return 0;
    }
    else
    {
        return radix13(n / 10) * 13 + (n % 10);
    }
}

int main()
{
    for (unsigned int i = 10; ; ++i)
    {
        if (radix13(i) % i == 0)
        {
            std::cout << i << std::endl;

            break;
        }
    }
}

しまった、radix13の返値の型はunsigned intに置き換えてください。

誰かと被ってると思われ．

Rubyって次期バージョンからcontinuation無くなるんだっけ？
使って書いてみようかと思ったけど…

最小値を一発で求めることができるような式って，立てられるかな…

def search_cmn_13
  n = 10
  loop {
    n13 = n.to_s.to_i(13)
    return n if n13 % n == 0
    n += 1
  }
end
puts search_cmn_13

なるほど．上手い

strtolって便利そうですね。

#include <iostream>
using namespace std;

int main()
{
	int itmp;
	int imax = 10000;
	for(int idec=10;idec<imax;idec++)
	{
		char str[5];
		sprintf(str,"%d",idec);
		int i13 = strtol(str, NULL, 13);
		if (i13%idec==0)
		{
			cout << idec << endl;
			break;
		}
	}
}

ついでにC版を、、、と思ったら、#267に既にある上にそちらの方がよりシンプルですね。でもせっかくなので投稿します。

#include <stdio.h>
#include <stdlib.h>

int main()
{
	int i13, idec, itmp;
	int imax = 10000;
	for(idec=10;idec<imax;idec++)
	{
		char str[5];
		itoa(idec, str,10);
		i13 = strtol(str, NULL, 13);
		if (i13%idec==0)
		{
			printf ("%d", idec);
			break;
		}
	}
	return 0;
}

from itertools import count

class NotFound(Exception): pass

def first(predicate, iterable):
    for i in iterable:
        if predicate(i): return i
    raise NotFound

def search():
    pred = lambda i: int(str(i), 13) % i == 0
    return first(pred, count(20))

無駄に再帰。

public class Thirteen {
    public static void main(String[] args) throws Exception {
        if (args.length != 1) {
            throw new Exception("引数がないよ.");
        }
        int i = Integer.parseInt(args[0]);
        int t = Integer.parseInt(String.valueOf(i), 13);
        if (t % i == 0) {
            System.out.println(t);
            return;
        } else {
            main(new String[]{String.valueOf(i + 1)});
        }
    }
}

Rのas.integerには基数変換の機能がないのかな・・・

for(i in 10:10000){
    if((as.integer(unlist(strsplit(as.character(i), ""))) %*% rep(13, nchar(i))^c((nchar(i)-1):0)) %% i == 0)
    break
}
print(i)

module doukaku;
private import std.stdio;
private import std.string;
private import std.regexp;
int radix13 () {
    for (long i=10; 1; i++) {
        char[] radix13 = toString(i, 13u);
        if (std.regexp.find(radix13, r"^\d+$") != -1) {
            long radix13_int = atoi(radix13);
            if (i % radix13_int == 0) return i;
        }
    }
}

void main() {
    writefln(radix13());        // 3114
}

function radix13()
  i = 10
  while true do
    str = tostring(i)
    r13 = tonumber(str, 13)
    if math.mod(r13, i) == 0 then
      return i
    end
    i = i+1
  end
end

print(radix13())                -- 1557

シンプルにループで

finalNumber = 10000;
base = 13;
for n=10:finalNumber
  if rem(base2dec(num2str(n), base), n) == 0
    disp(n);
    break;
  end
end

そういやこれやってなかったなあ

def _find13x(n:Int):Int = Integer.parseInt(n.toString, 13)%n match {
  case 0  => n
  case _  => _find13x(n+1)
}
def find13x = _find13x(10)

println(find13x)

rubikitchさんのを見てみたらparse-integerで基数指定する方が素直でした。
(print (answer))

(defun read-as-base (n base)
  (let ((*read-base* base))
    (read-from-string (prin1-to-string n))))

(defun answer ()
  (loop for i from 10
        do (if (zerop (mod (read-as-base i 13) i))
             (return i))))

一般にp進法とq進法の見た目が同じときにn倍になる関係を持つ数を出力するプログラムです。

#!/usr/bin/python
"""
>>> digits(10, 10)
[1, 0]
>>> digits(2, 7)
[1, 1, 1]
>>> value(10, [1, 0])
10
>>> value(2, [1, 1, 1])
7
>>> f(2, 3, 2)
[[1, 0, 1], 5, 10]
"""
def digits(p, x):
  d = x % p
  x = x / p
  if x:
    ds = digits(p, x)
    ds.append(d)
    return ds
  return [d,]

def value(q, ds):
  value = 0
  qq = 1
  ds.reverse()
  for d in ds:
    value += d * qq
    qq *= q
  return value

def f(p, q, n):
  assert(p < q)
  assert(n > 1 and isinstance(n, int))
  x = 1
  while x * n <> value(q, digits(p, x)):
    x = x + 1
  return [digits(p, x), x, value(q, digits(p, x))]

print f(10, 13, 2)

import doctest
doctest.testmod()

C:\>php -r "if(0){print 1;}else{print 2;}"
2

0はfalse扱いみたいですね。Pythonと同じ。

なるほど、無限リストを使うのなら
こういう書き方もアリですね。

1
2
3

>>> from itertools import count, ifilter
>>> (x for x in count(10) if int(str(x), 13) % x == 0).next()
1557

var numObj = new Number();
for (var i = 10; i<10000; i++) {
  numObj = i;
  // numObjをStringに変換してnum10に格納
  var num10 = numObj.toString(i);
  // num10を13進数に変換してnum13に格納
  var num13 = parseInt(num10, 13);
  if (num13%num10 == 0) {
    trace("10進数："+num10);
    trace("13進数："+num13);
    break;
  }
}

function search(){
  for (i : 10..1000000){
     n13 = int(string(i), 13)
     if (n13%i == 0) return i
  }
}
println(search())

匿名ですみません。
LL魂でその気になったくせにSQLです。

DROP TABLE  if exists D;
CREATE TABLE D (n int NOT NULL);
INSERT INTO D VALUE (0);
INSERT INTO D VALUE (1);
INSERT INTO D VALUE (2);
INSERT INTO D VALUE (3);
INSERT INTO D VALUE (4);
INSERT INTO D VALUE (5);
INSERT INTO D VALUE (6);
INSERT INTO D VALUE (7);
INSERT INTO D VALUE (8);
INSERT INTO D VALUE (9);

DROP TABLE if exists N;
CREATE TABLE N as
  SELECT
    a.n as n1
  , b.n as n10
  , c.n as n100
  , d.n as n1000
  , e.n as n10000
  FROM
    D a
  , D b
  , D c
  , D d
  , D e
;

SELECT *
FROM
  (SELECT
    (n1 + (n10 * 10)
      + (n100 * 100)
      + (n1000 * 1000)
      + (n10000 * 10000)
    ) as x10
  , (n1 + (n10 * 13)
      + (n100 * 13 * 13)
      + (n1000 * 13 * 13 * 13)
      + (n10000 * 13 * 13 * 13)
    ) as x13
  FROM N
  ) as n
WHERE
  x10 >= 10
  AND
  x13 % x10 = 0
ORDER BY x10
LIMIT 1
;

BEGIN {
	for (x=10; !check(x); x++) ;
	print x; exit;
}
function check(x,  n,k,i)
{
	n = 0;
	k = length(x);
	for (i=1; i<=k; i++) n = n * 13 + substr(x,i,1)
	return (n == x * 2)? 1 : 0;
}

可読性は考慮していません☆

#include<stdio.h>
int main(void){
  int i=9,j,k,l;
  do
    for(j=++i,k=i*2,l=1;j>0;k-=j%10*l,j/=10,l*=13);
  while(k);
  printf("%d\n",i);
  return 0;
}

初期位置を意図的に1111にしています。500回しか計算できないようなので。

#include<iostream>

const int BASE = 13;
const int DEC = 10;

template <int n>
struct TransTri
{
    enum { value = BASE * TransTri<n/DEC>::value + n%DEC };
};
template <>
struct TransTri<0>
{
    enum { value = 0 };
};

template <int n, bool res>
struct __solv
{
	enum { value = __solv<n+1, TransTri<n>::value%n == 0>::value };
};
template <int n>
struct __solv<n,true>
{
	enum { value = n - 1 };
};

template <int n>
struct Solv
{
	enum { result = __solv<n,false>::value };
};

int main()
{
	std::cout << Solv<1111>::result << std::endl;
	return 0;
}

無駄に無限リストにしてみました。
遅くて３個目が見つからない。。。

// xtal 0.9.7.1 の inject はバグっているので自作。
Iterator::reduce: method(init, fn){
    result: init;
    this {
        result = fn(result, it);
    }
    return result;
}


Int::to_i13: method {
    return this.to_s.split("").reduce(0, |r,e| r * 13 + e.to_i);
}

resolver: fiber {
    for (i: 10; true; i++) {
        if (i.to_i13 % i == 0) {
            yield i;
        }
    }
}

resolver.take(1).to_a[0].p;

ループを使う方法は既に出ているので、ループを使わない方法で書いてみた。順番にチェックするのではなく全部計算するので、調べる範囲の上限を与えなければいけないしメモリも食う。条件を満たす最小の数を返せというこの問題に対しては効率のいい方法とは言えない。例えばmからnまでの整数で条件を満たすものを全て見つけろ、というような問題だとするとループより速いかも? 最後2行のコメントを外すと13進数とみなす場合と10進数とみなす場合との比をグラフに表示する。この比が整数となる数字列が条件を満たすことになる。最後から3行目のminを外すと範囲内の全部の答を出力する。

function n = finddoubleinb13(rmax)
% Returns a sequence of digits that is twice bigger in base 13 than in base 10.
% The numbers from 10 to rmax in base 10 will be checked (ja.doukaku.org Q14).
n10 = (10:rmax)';
n13 = base2dec(num2str(n10),13);
idx = find(~mod(n13(:),n10(:)));
n = min(n10(idx));
% plot(n10,n13(:)./n10(:))
% grid on

とりあえず総当たりで

function to-dec($num, $r)
{
	$ret = 0
	$p = 1
	$s = [string]$num
	for ($i = $s.length -1; $i -ge 0; $i--) {
		$ret += [int][string]($s[$i]) * $p
		$p = $p * $r
	}
	$ret
}

for ($i = 10; ; $i++) {
	$r = to-dec $i 13
	if (($r % $i) -eq 0) {
		$i; break
	}
}

普通に。

Dim num As Integer = 10
Do
    Dim tmp As Integer = num
    Dim val As Integer = 0
    For i As Integer = 0 To num.ToString.Length - 1
        val += (tmp Mod 10) * 13 ^ i
        tmp \= 10
    Next
    If val Mod num = 0 Then
        Console.WriteLine(num)
        Exit Do
    End If
    num += 1
Loop

Ocamlの二番煎じ。

fun thirteen x =
let
  fun loop (0, x, t) = t
    | loop (q, x, t) =
    loop (q div 10, x * 13, t + x * (q mod 10))
in
  loop (x, 1, 0)
end

fun comp x =
  if (thirteen x) mod x = 0 then x else comp (x + 1);

println (Int.toString (comp 10))

> junk <- sapply(10:10000, foo)
[1] 1557
[1] 1560
[1] 1614

foo <- function(x) {
    d <- as.integer(unlist(strsplit(as.character(x), "")))
    j <- sum(d*13^((length(d)-1):0))/x
    if (j == floor(j))  print(x)
}
junk <- sapply(10:10000, foo)

これでいける筈。

use strict;

for(my $i = 10; $i <= 10000; $i++) {
    for(my $c = 0, $_ = $i; /(\d)(\d*)/;) {
        $c = 13 * $c + $1;
        ($_ = $2) || ($c % $i) || printf("%d (%d)\n", $i, $c);
    }
}

    #i = 10;
    while( true ) {
        call convert #i;
        if ( ##return == ( #i * 2 ) ) {
            break;
        }
        #i = #i + 1;
    }
    message str( #i );
    endmacro;

convert:
    $$val = str( ##1 );
    ##result = 0;
    ##i = 0;
    while( ##i < strlen( $$val ) ) {
        ##result = ##result * 13 + val( midstr( $$val, ##i, 1 ) );
        ##i = ##i + 1;
    }
    return ##result;

#module
#defcfunc convert int x
    val = str( x )
    result = 0
    repeat strlen( val )
        result *= 13
        result += peek( val, cnt ) - '0'
    loop
    return result
#global

    repeat , 10
        if ( convert( cnt ) == ( cnt * 2 ) ) {
            dialog str( cnt )
            break
        }
    loop

短くしてみました。

def search_baisu(n = 13, _xbai = 2, _i = 0)
  while (_i += 1).to_s.to_i(n) != _xbai * _i
  end
  _i
end

p search_baisu  # --> 1557

ワンライナー童貞を捨てた記念に投稿します。

13進数に変換する部分はid:nekoruriさんの投稿を参考にしました。

1	perl -M'List::Util qw/reduce first/' -le 'print first {$_} grep {!(sub{reduce{13*$a+$b}split //}->($_)%$_)} 10..10000'

いろいろと無駄が多かったのでちょこっと直しました。

あと余計なスペースを詰めて余計に読みにくくしてみました。

1	perl -M'List::Util qw/reduce first/' -le 'print first{!((reduce{13*$a+$b}split//)%$_)}10..10000'

   g 10000
1557 1560 1614

1 2	f=:3 :'0=(10&#.\|13&#.)10(#.^:_1)y' g=:3 :'10+I.f"0]10+i.y'

if, while文の両方を後置してみたけど正常に動作した. 初期値を入れるのが冗長っぽいけど削るアイデアが沸かなかった.

1 2	d = 9 raise "#{d}: Found!" if "#{d += 1}".split(//).inject(0){\|i,j\| i.to_i*13 + j.to_i}.modulo(d) == 0 while 1

PostScript で。カバレッジ稼ぎ。一旦文字列に変換して処理させています。14行の exit を外すとループが終わるまで探索します。

%!PS

/TestVal { % <integer> TestVal <bool> 
    dup
    10 string cvs
    (13#          ) % for 10 digits
    dup 3 4 -1 roll putinterval
    cvi
    exch mod 0 eq
} bind def

% -------------- Main ----------------
10 1 99999999 {
    dup TestVal {(ans = ) print = exit} { pop } ifelse
} for

Factor です。ちなみに一行にするとこうなります。

: f dup number>string 13 base> over mod 0 = [ ] [ 1 + f ] if ; 10 f .

USING: kernel math math.parser strings prettyprint ;

: base13 ( n -- n13 )
  number>string 13 base> ;

: it? ( n13 n10 -- t/f )
  mod 0 = ;

: f ( n -- n )
  dup base13 over it?
  [ ] [ 1 + f ] if ;

10 f .

Adaで適当に

with Ada.Text_Io;
procedure Twice is
begin
   for I in 10..10000 loop
      declare
         Str:String:=Integer'Image(I);
         Num:Natural:=Natural'Value("13#"&Str(Str'First+1..Str'Last)&"#");
      begin
         if Num=I*2 then
            Ada.Text_Io.Put_Line(Integer'Image(I)&" => "&Integer'Image(Num));
         end if;
      end;
   end loop;
end Twice;

1
2
3

i := 10
while(i asString fromBase(13) % i != 0, i = i + 1)
i println

徒然なるままにつくってみました。ま、小さいコードですよね。

10.upto(9999) { 
nagasa = it.toString().toList().size
youso =  it.toString().toList()
jyusanshin = 0
for (x in 1 .. nagasa) {
    jyusanshin = jyusanshin + (youso[-x].toInteger())*(13.power(x-1))
}
if (jyusanshin%it==0) { 
    println "Found: "+it +"("+jyusanshin+")"
    System.exit(0)
    }
}

なんで nagasa を先に代入するのかな。

erl_evalと　Erlang特有のN進法表記(N#M, 基数Nは36以下)を
使ってみたらどうだろうと思って書いてみました。
基数に上限があるので汎用性に欠けると思います。

プログラムを bai13.erl というファイル名で保存して、
$ erl -noshell -s bai13 getfirst -s init stop
のようにして起動します。

see: Erlangのevalってこうやるのか

-module(bai13).
-export([getfirst/0]).

getfirst() ->
    loop(10).

loop(N) ->
    case (eval("13#" ++ integer_to_list(N) ++ ".") rem N) of
        0 -> io:format("~p~n",[N]);
        true -> loop(N + 1)
    end.

eval(Expr)->
    {ok, Tokens, _}=erl_scan:string(Expr),
    {ok,[Expression]} = erl_parse:parse_exprs(Tokens),
    {value, Ret,_} = erl_eval:expr(
        Expression ,erl_eval:bindings(erl_eval:new_bindings())
        ),
  Ret.

program Multiple13;

var
    base10    :Integer;

function ToBaseN(base,number:Integer):Integer;
begin
    if number = 0 then
        ToBaseN := 0
    else
        ToBaseN := ToBaseN(base,number div 10) * base + number mod 10
end;

begin
    base10 := 10;
    while ToBaseN(13,base10) mod base10 <> 0 do
        base10 := base10 + 1;
    WriteLn(base10)
end.

LLVMアセンブリ (32bit) で。<a href="http://ja.doukaku.org/comment/257/">#257</a>の移植です。

declare i32 @printf(i8*, ...)

@msg = internal constant [15 x i8] c"13n:%d 10n:%d¥0A¥00"

define i32 @main() {
    %msgp = getelementptr [15 x i8]* @msg, i32 0, i32 0
    %i = alloca i32
    store i32 10, i32* %i
    br label %loop_head

loop_head:
    %ival = load i32* %i
    %cont = icmp slt i32 %ival, 10000
    br i1 %cont, label %loop_body, label %return

loop_body:
    %val13 = call i32 @to13(i32 %ival)
    %target = mul i32 %ival, 2
    %res = icmp eq i32 %val13, %target
    br i1 %res, label %return, label %loop_next

loop_next:
    %ival_next = add i32 %ival, 1
    store i32 %ival_next, i32* %i
    br label %loop_head

return:
    %reti = load i32* %i
    %reti2 = mul i32 %reti, 2
    call i32 (i8*, ...)* @printf(i8* %msgp, i32 %reti, i32 %reti2)
    ret i32 0
}

define i32 @to13(i32 %default) {
    %n = alloca i32
    store i32 %default, i32* %n
    %retval = alloca i32
    store i32 0, i32* %retval
    %dig = alloca i32
    store i32 10000, i32* %dig
    br label %calc

calc:
    %t1 = load i32* %retval
    %t2 = mul i32 %t1, 13
    %nval = load i32* %n
    %digval = load i32* %dig
    %t3 = sdiv i32 %nval, %digval
    %t4 = add i32 %t2, %t3
    store i32 %t4, i32* %retval
    %t5 = srem i32 %nval, %digval
    store i32 %t5, i32* %n
    %t6 = sdiv i32 %digval, 10
    store i32 %t6, i32* %dig
    %cont = icmp sgt i32 %t6, 0
    br i1 %cont, label %calc, label %return

return:
    %r = load i32* %retval
    ret i32 %r
}

iで10から10000まで繰り返す
    a=0;b=iを文字列分解
    jで(iの文字数-1)から0まで繰り返す
        a=a+b[回数-1]*13^j
    もし(a = i*2)ならば
        iを表示して抜ける

シンプルに

1
2
3

import Char
f n = (mod (foldl1 (\a b->a * 13+b)$map digitToInt $show n) n) == 0
main = print $ head $ filter f [10..]

意味もなく短くしてみました

1 2	import Char main=(print. head.filter(\n->(mod(foldl1((+).(* 13))$map digitToInt$show n)n)==0)) [10..]

for文でごり押しの方が速度的には速いのが残念ですが･･･。

せっかくなのでLINQ記法。

Haskellみたいに無限数列が定義できればもっとすっきりするのですが。

    class Program
    {
        static void Main(string[] args)
        {
            for (int i = 10; ; i++)
            {
                if (Create13BaseNum(i) % i == 0)
                {
                    Console.WriteLine(i);
                    break;
                }
            }
            Console.ReadLine();
        }

        public static int Create13BaseNum(int num)
        {
            IEnumerable<char> numCharAry = num.ToString().ToCharArray().Reverse();
            return (int)numCharAry.Select((n, i) => Math.Pow(13, i) * (n - 48)).Sum();
        }
    }

nを13以外にすると別の進数にも対応します.

i = 10
n = 13
while True :
    j = reduce(lambda x, y : n * int(x) + int(y), str(i), 0)
    if j % i == 0 :
        break
    i += 1

print str(j) + "[" + str(n) + "] = " + str(i) + "[10]"

whitespaceで。

該当する数が見つかるまで10から順番にチェックしているだけです。

PHP勉強中

<?php
print <<< END_DOC
<HTML>
<HEAD><title>doukaku14</title>
</HEAD><BODY>
END_DOC;

function doukaku14($max_n)
{
    for($i = 10; $i <= $max_n; $i++){
        $Num13 = intval(strval($i), 13);
        
        if(($Num13 % $i) == 0){
            print "$i";
            return;
        }
    }
    print "not found";
}

doukaku14(10000);

print <<< END_DOC
</BODY>
</HTML>
END_DOC;
?>

#ifndef powf
 #include "hspmath.as"
 #define global pow powf
#endif

#module

#define ctype cwhich_int(%1,%2,%3) \
    ( ((%2) * ((%1) != 0)) || ((%3) * ((%1) == 0)) )

//------------------------------------------------
// 数字列を10進数値に変換する
//------------------------------------------------
#defcfunc ChangeRadix_toDigit str _sInput, int fromRadix,  \
    local sInput, local result
    
    if ( fromRadix <= 0 ) { return 0 }
    
    sInput = getpath(_sInput, 16)
    len    = strlen(sInput)
    result = 0
    
    repeat len
        c       = peek(sInput, len - (cnt + 1))
        n       = cwhich_int(c >= 'a', c - 'a' + 10, c - '0')
        result += n * int(powf(fromRadix, cnt))
    loop
    
    return result
    
#global

*main
    // 総当たりで解く
    repeat , 10
        snum = str(cnt)
        
        numOf13rdx = int( ChangeRadix_toDigit(snum, 13) )
        numOf10rdx = cnt
        
        if ( numOf13rdx \ numOf10rdx == 0 ) {
            x = cnt
            break
        }
    loop
    
    dialog "A. x = "+ x
    end

program main
     implicit none
     integer:: ix; ix = 11
     do while((.not.isDividable(ix)))
         ix = ix + 1
     end do
     print *, ix
     contains
     function asBase13(x)
         integer, intent(in)::x
         integer::asBase13
         integer::hun,dec,one
         hun = x/100;
         dec = (x - hun*100)/10;
         one = x - 10*dec
         asBase13 = 13*13*hun + 13*dec + one
     end function
     function isDividable(x)
         integer,intent(in):: x
         logical:: isDividable
         integer::b13,div
         b13 = asBase13(x)
         div = b13/x
         isDividable = (b13 .eq. div * x)
     end function
end program

DouKaku?

倍数になる13進数

Posted feedbacks - Flatten

Index

Feed

Other

Link

Pathtraq