Kawazoe(@riverplus)さんのCodeIQの問題です。
問題のページへのリンクが切れていますが、次のような問題です。
問題
与えられた数までの整数を二進数としたときその1の数の総数を答えてください
【解答】
・第1問:F(10^3) = 4938
・第2問:F(10^10) = 164293127179
こちらにも情報があります。
->https://posfie.com/@riverplus/p/40uN35X?page=2
->https://posfie.com/@riverplus/p/40uN35X (2026.11.12)
(web検索で偶々当たったのを書いてしまいました。今見に行って気が付きました)
解法
0 0 0 0 2進数を縦に並べるとk桁目の0と1が
0 0 0 1 2^(k-1)個ずつ続くことに気が付きます。
0 0 1 0 k-1桁までが0から2^(k-1)-1を繰り返しますので当然です。
0 0 1 1 これを利用して解きます。
0 1 0 0
0 1 0 1 k桁目の0,1の並びをそれぞれ一組にして
0 1 1 0 合わせて何組あるか計算すると
0 1 1 1 (d,m)= (x+1)) divmod 2^(k-1)としてd組となります。
1 0 0 0 そのうち1の組の数は(d div 2)個で
それぞれに1が2^(k-1)個含まれますので、
1の数は(d div 2)*2^(k-1)です。
端数の1の数はdが偶数なら次の数字が0なので0個、
奇数なら次から1が続くのでm個です
#julia ver 1.41,1.53,1.85,1.12.1
function solve(n,a)
sum ,x = 0 , 1
while(x <= n)
(d,m) = divrem(n+1,x) #0の部分を足す
sum += div(d,2) * x
if isodd(d) sum += m end
x *= 2
end
s = sum == a ? "ok " : "no "
println(s,sum)
end
solve(10^3,4938)
solve(10^10,164293127179)
最近古い言語のio、iconの後継のunicon、prologの発展系のpicatで遊んでいます。
そこで今回は簡単なコードでもあるし、Picatで書いてみました。
PicatについてAIさんにまとめてもらいました。
Picat:Prologの「探索力」と手続き型の「書きやすさ」を統合した言語
B-Prologの開発者によって設計されたPicatは、Prologをベースに、決定的な
実行(コミット)と強力なループ構文、そして強力なソルバーを内蔵した言語です。
■ 4つのルール記法:実行戦略の使い分け
| 記法 | 種類 | 特徴 |
|---|---|---|
| Head = Result | 関数型 | 戻り値を返す決定的な定義。代入式で呼び出し可能。 |
| Head => Body | コミット型 | 条件一致でルール固定。バックトラックせず高速。 |
| Head ?=> Body | 非コミット型 | 実行後、失敗時は「次のルール」も試すガード付き探索用。 |
| Head :- Body | Prolog型 | 伝統的なホーン節。全解を網羅するレガシー互換。 |
■ Picatを最強にする3つの武器
- 強力な制御構造
foreach等のループ、ifやcond、リスト内包表記、破壊的代入(:=)を備え、
手続き型の感覚で記述可能。
- 制約論理プログラミング (CLP)
cp,sat,mipモジュールを内蔵。数独から複雑なスケジュール最適化まで、
制約を記述するだけで超高速に解く。
- テーブル化 (Tabling)
述語にtableと宣言するだけで計算結果を自動キャッシュ。
再帰的な動的計画法(DP)を、メモ化のコードなしで一瞬で実装可能。
Picatでの解法
最初の0の列を消して1と0の並び一つずつを合わせて一組とする方法もあります。
k桁目は下位から2^(k-1)個がなく、また一組の数が2^kとなりますので、
(d,m)=(x-2^(k-1)+1) divmod 2^kとすると、割り切れる部分の1の数はd*2^(k-1)個。
端数の1の数はm>2^(k-1) なら2^(k-1)個,m=<2^(k-1)ならm個 です。
今回はprologい寄せて述語形式で書きました。
なおPicatはweb上のplayground類が見つからず、AIに聞きながら
WSL + Picat + VsCode + VSC-Picat + Code Runner
の環境を作って走らせています。設定は最低限ですが下記で何とか動いています。
"picat.executablePath": "/home/***/Picat/picat"
"code-runner.executorMap":
"picat": "cd \$dir && ~/Picat/picat $fileName"
"code-runner.runInTerminal": true
(Picatの部分のみ抽出)
Code-Runnuerのrunボタン あるいは右クリックして 「Picat:run doccument」で
consultとmainの実行がなされます。
またはteaminalで「picat」を入力してpicatに入り「cl('path/filename').」
でmain以外の関数や述語も実行できます。
% Picat v 3.9#7
%VsCode + WSL + VSC-Picat + Code Runner
main => %mainを自動で選択
Data = [[10**3,4938],[10**10,164293127179]],
foreach([N,A] in Data)
if solve(N,R) then
Str = cond(R == A, " ok ", " no "),
printf(" %s %w->%w%n", Str, N, R)
else
printf(" fail %w%n", N)
end
end.
solve(N,R) =>
Sum = 0, % = 変数に値を確定させる
X = 1,
while(X<=N)
D := (N-X+1) div (X*2), % := 値を変更(更新)する
M := (N-X+1) mod (X*2),
Sum := Sum + D*X + min(M,X),
X := X*2,
end,
R = Sum.
---