この記事は ひとりアドベントカレンダーRosettaCodeで楽しむプログラミング Advent Calendar 2025の4日めの記事です。
定義
5より大きい素数 $p$ は、$p-1$ 桁のrepunitを割りきる、らしい。
$k$ が合成数なのに $k-1$ 桁のrepunitを割りきるとき、それを deceptive number という。
タスク
小さい方から少なくとも10個、deceptive number を見つけよ。
考える
例に出ているものでも $k = 91$ と巨大な数になるので、Int では直接扱えない。
しかし、Integer で扱うのもあまり気が利かない。
$k-1$ 桁のrepunitを作るために、0または1から「10倍して1を足す」という操作を繰り返すときに、これをモジュロ$k$で行えば、repunitを$k$で割った余りが直接求められるので、これが0になるなら deceptive number だとわかる。
import Data.Numbers.Primes
isDeceptive :: Int -> Bool
isDeceptive k
| isPrime k = False
| otherwise = 0 == iterate (flip mod k . succ . (10 *)) 1 !! (k - 2)
-- 1は合成数でない
-- 2,3は素数
-- 奇数でないと奇数を割りきることはできないから4はない
-- 5,7も素数
task = take 10 $ filter isDeceptive [9, 11 ..]
ghci> task
[91,259,451,481,703,1729,2821,2981,3367,4141]
(0.51 secs, 932,781,984 bytes)
今日は小ネタでした。
延長戦
公開直前になって見返して、評価されているWren版とやらを見てみる。
…GMP使って直接計算している。
それでいて62番目97681までを0.179秒で計算できると。
真似してみる。
deceptives :: [Integer]
deceptives =
[ n
| (n, r) <- zip (iterate (2 +) 17) (iterate ((11 +) . (100 *)) 1111111111111111)
, not $ isPrime n, mod n 3 /= 0, mod n 5 /= 0, mod r n == 0
]
ghci> take 62 deceptives
[91,259,451,481,703,1729,2821,2981,3367,4141,4187,5461,6533,6541,6601,7471,7777
,8149,8401,8911,10001,11111,12403,13981,14701,14911,15211,15841,19201,21931,22321
,24013,24661,27613,29341,34133,34441,35113,38503,41041,45527,46657,48433,50851
,50881,52633,54913,57181,63139,63973,65311,66991,67861,68101,75361,79003,82513
,83119,94139,95161,97273,97681]
(0.86 secs, 3,356,538,368 bytes)
ghci> take 30 $ filter repKisDeceptive [9, 11 ..]
[91,259,451,481,703,1729,2821,2981,3367,4141,4187,5461,6533,6541,6601,7471,7777
,8149,8401,8911,10001,11111,12403,13981,14701,14911,15211,15841,19201,21931]
(11.06 secs, 27,742,882,776 bytes)
はい、ぜんぜんかないませんでした。
Discussion ページを覗く
Wrenにはもうひとつの実装があって、こちらはbigintも必要ない、と書いてある。
しかし自分のやつのように遅いプログラムではないようだ。
Discussionページをちゃんと読んだ方がよさそうだ。
n桁のrepunitを $R_n$ と表す。$d$ が $n$ を割りきることを $d \mid n$ と表す。
- repunitの1の位は1なので、5で割り切れない。なので5の倍数はdeceptive numberにならない。
- 2でも同様で、偶数はdeceptive numberにならない。
- nが3の倍数のとき、$R_{n-1}$の数字の和は $n-1$ で、これは決して3の倍数にならないので、$R_{n-1}$ は3で割り切れない。なので3の倍数はdeceptive numberにならない。
- $7^2$ より小さい合成数は2,3,5のいずれかの倍数しかないので、nを線形探索する初期値は49で十分。
- repunitを作るひとつのやり方、$10^n - 1 = 99\cdots99 = 9R_{n-1}$ を逆に使うと
$n \mid R_{n-1} \Leftrightarrow 9n \mid 9 R_{n-1} \Leftrightarrow 9 R_{n-1} + 1 \equiv 1 \bmod 9n$
これならモジュロでべき乗をする計算が使えるので、repunitを一桁ずつ構築しながらモジュロをとる、とやらずに判定できる。
最後のやつ、OEISだと $9n$ で割って、Rosetta Codeでは n が3の倍数でないことを保証してから n で割っている。
除数は大きい方が計算速くなる気がするので $9n$ で考えよう。
deceptives3 :: [Int]
deceptives3 = filter isDeceptive2 [49, 51 ..]
isDeceptive2 :: Int -> Bool
isDeceptive2 n = odd n && mod n 3 /= 0 && mod n 5 /= 0 &&
not (isPrime n) && modPower (9 * n) 10 (pred n) == 1
modPower :: Int -> Int -> Int -> Int
modPower base a b = foldl' mul 1 [p | (True, p) <- zip bs ps]
where
mul x y = mod (x * y) base
bs = map odd $ takeWhile (0 <) $ iterate (flip div 2) b
ps = iterate (\x -> mul x x) a
ghci> take 62 deceptives3
[略]
(0.72 secs, 1,554,556,152 bytes)
小ネタじゃありませんでした。