算数パズルしようや

**風吹けば名無し** · 2023/09/21(木) 17:20:45.28

ある整数Nが与えられます。
「Nを、Nの各桁和か各桁積に置き換える」操作をちょうど100兆回行ったあと、N=1にできるか判定してください。

各桁和: 217→2+1+7=10
各桁積: 217→2×1×7=14

これ解けるんか？

**風吹けば名無し** · 2023/09/21(木) 17:21:06.52

**風吹けば名無し** · 2023/09/21(木) 17:21:32.28

N=5 のときは、操作してもN=5から変わらないから答えはNoやな

**風吹けば名無し** · 2023/09/21(木) 17:23:36.98

数学やろ
知らんけど

**風吹けば名無し** · 2023/09/21(木) 17:24:33.65

>>4
それはそう

**風吹けば名無し** · 2023/09/21(木) 17:25:18.61

各桁積置換が曲者すぎるわ
数字が全然小さくならん

**風吹けば名無し** · 2023/09/21(木) 17:25:33.90

だいたい無理そうやね

**風吹けば名無し** · 2023/09/21(木) 17:26:14.88

>>7
ほんまか？割とできそうやない？

**風吹けば名無し** · 2023/09/21(木) 17:26:22.62

和と積の使い分けは1にするために自分で好きに選んでいいんでしょ？

**風吹けば名無し** · 2023/09/21(木) 17:27:15.28

>>9
ええで
たとえば11は各桁積を取り続けることで1に収束できるから、答えはYes

**風吹けば名無し** · 2023/09/21(木) 17:28:17.24

とりあえずNは1億未満で考えるか

**風吹けば名無し** · 2023/09/21(木) 17:29:08.02

質問や
一桁の時どうするんや？
2のとき
和　2→2+0=2
積　2→2×0=0
って認識で合ってる？

**風吹けば名無し** · 2023/09/21(木) 17:29:10.00

>>8
1以外の一桁になったらゲームオーバーで、掛けても足しても大体減るから何兆回も粘れないんちゃうかな
第一印象やけどな

**風吹けば名無し** · 2023/09/21(木) 17:29:20.60

あーでも行けそうやけどな
各桁和を取った時の値の減り方がえげつないから、実質各桁積を取ったときだけ追えば良いし

**風吹けば名無し** · 2023/09/21(木) 17:29:56.45

1や11でも正解じゃないん？

**風吹けば名無し** · 2023/09/21(木) 17:29:59.04

積か和を都度選択して、あらゆる選択の組み合わせの中に条件を満たすものがあるかどうかの判定？

**風吹けば名無し** · 2023/09/21(木) 17:30:35.74

>>12
一桁の数字は、各桁和も各桁積もNのままや
N=2なら、どちらの操作を選んでもN=2のままやな

**風吹けば名無し** · 2023/09/21(木) 17:31:19.20

>>15
最初のNが1や11なら、答えはYesやな
じゃあNが42876415ならどうや？

**風吹けば名無し** · 2023/09/21(木) 17:31:28.08

積とると素因数が2,3,5,7だけになるのポイントそうやな

**風吹けば名無し** · 2023/09/21(木) 17:31:45.82

100兆回までにじゃなくてちょうど100兆回ってのが曲者やな
知らんけど

**風吹けば名無し** · 2023/09/21(木) 17:32:17.92

>>16
そうや
最初にNが与えられるから、最も都合よく操作した時にN=1にできるか判定しろって感じ

**風吹けば名無し** · 2023/09/21(木) 17:33:09.48

>>20
別に「ちょうど」は要らんかったわ
Nは単調減少することが示せるし

**風吹けば名無し** · 2023/09/21(木) 17:33:58.40

全てのNでこれが成立するのかって問いなら否
それとも成立するNをいっぱい探してみようってことなのか？

**風吹けば名無し** · 2023/09/21(木) 17:34:18.55

あーなんか解けたなこれ
事前にN<1000くらいは小さい値から全探索しておけばいいのか

**風吹けば名無し** · 2023/09/21(木) 17:34:30.38

1,10,100,1000
1,11,111,1111をつくってい感じやな

**風吹けば名無し** · 2023/09/21(木) 17:35:16.89

そんな答えでいいんか

**風吹けば名無し** · 2023/09/21(木) 17:35:34.44

これ競プロの問題とかちゃうの

**風吹けば名無し** · 2023/09/21(木) 17:35:37.47

>>23
だいたいそんな感じや
たとえば「Nが766287459のとき、操作後1にできる？」みたいな判定問題やな

**風吹けば名無し** · 2023/09/21(木) 17:35:59.97

てかこれ競技プログラミングの問題？

**風吹けば名無し** · 2023/09/21(木) 17:36:14.65

>>27
競プロやなこれ
Nを指定すればよかったわ

**風吹けば名無し** · 2023/09/21(木) 17:37:01.65

Nが123456789のとき、操作後1にできますか？
みたいな具体的な出題にすべきやったわ

**風吹けば名無し** · 2023/09/21(木) 17:39:20.70

多倍長整数を容認すれば、N<10^100くらいまでは解けそう
各桁積のときの収束速度をちゃんと確認しとらんから、限界は分からんが

**風吹けば名無し** · 2023/09/21(木) 17:40:02.51

>>29
競プロになってしまったわ
オリジナル問題

**風吹けば名無し** · 2023/09/21(木) 17:41:42.92

10^n くらいの各桁積の最大が 9^n だから (9/10)^n くらいで落ちていくんやない？

**風吹けば名無し** · 2023/09/21(木) 17:42:40.73

>>34
そうやな
ただ多倍長整数が絡むから実計算速度は遥かに遅そうや

**風吹けば名無し** · 2023/09/21(木) 17:45:47.77

たくさん操作した時にN=1にできるか？
という表を下からのDPで前計算しておけば、各桁和のときはO(1)で判定可能
あとは愚直に各桁積を取り続ければいい