グーグルの入社問題ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

整数nが与えられたとき、0からnの間の全ての数を書くのに必要とされる「1」の数を返す関数があります。
たとえば、『f(13)=6』になります。また、『f(1)=1』に注意。
『f(n)=n』となるような、2番目に大きいnを求めなさい。

共有NGBE

まーたデマか

メルカトル

おｋGoogle入社して来るはｗｗｗｗｗｗｗｗｗ

こいつがいる限り日本は安泰

∞ -1だろｗｗｗｗｗｗｗｗ簡単すぎｗｗｗｗｗｗｗｗｗｗｗ

答え

答える必要がありません。
なぜなら、グーグルは私を必要としてないからです。

こんなトンチみたいな問題だしてないで、数学とかの実力をはかる問題をだせよ。
卑怯だろ。

ユニバーサル

>>1
この整数問題糞簡単だな
証明なしでいいならいくつかのパターンを実験してれば答えでてくるんじゃないの？

ユニバーサルエンターテインメント

日本語でおｋ

球速の黒歴史ほじくり返すのはやめてあげろよ

感覚的にｎは100以下だろ。
後は全部列挙すりゃ終わりだろ。

2014年度電通入社問題
第一問　あなたは誰の血縁ですか
第二問　あなたの紹介者を書きなさい

最大が1
2番目は0

4

わろた
高校数学程度の問題でつまづくとか
嫌儲は文系Fランばかりとゆうことが証明はれたな

簡単すぎて答える価値もないわ
もっと難しい問題持って来い

f(13)=5じゃないのか

「なるほど分かりましたよ。あなたの普段の働きぶりが。これが答えです。」
といって解雇通知を渡す

>たとえば、『f(13)=6』になります

こらこらこら、1を返してないじゃん

>>16
池上彰が、NHKに入ったのは民放はコネがないと入れないからって言ってたな。
受からなくてもいいから試験だけでも受けさせてくださいって言っても門前払いだったとか。

0-9で1つ
10-19で1+10
20-29で1
30-39で1
・・・
99までで1*9+10=19か
100-199だとそれに100追加されるから
100-110の間に答えがあるんじゃね

数学教師のオレ、苦悶中

0
あんまり真面目に考える意味のない問題だな

いや0だろ
一瞬でわかったゾ

>>21
え？

問題の意味がわからん

感覚的に1しか等しくなる場合がなさそうだけど
答えあるのか？

低学歴視点だと一行目の日本語がおかしい意味不明なんだが
Googleはチョン

正解は>>17

6！

普通に0じゃね

f(n)-n<0 (n≧2)

これが証明できれば終わり。
あとはメルカトル速報に任せる

f(n)=nってなるのがn=1しかないんだが？
肝となるnだけ抜粋して書き出していったんだが、n=100でf=21
以降fがnの増え方よりも速度をあげて増える機会は、111や、121、131、211、311、1111くらいしかない

到底f=nとはなりえないんだが

n=1しか解が無い事を簡単に証明できるけど

二番目に小さいと誤読してる奴が結構いるような

>>37
n=-1,0

f(0)=0
f(1)=1
A.　１
おわり

f(3)=3

0〜3の間の1,2を表すために必要な１の数は
1(1)+2(1+1)=3

１０進数で書いてそれに含まれる「１」の話でしょ？これ。

>>40
なんでそこまで分かったのに解が１になった

>>32
ワロタ

負まで考えないでも一緒だからつまらん

答えをググればいいじゃん

簡単すぎ
http://up.pandoravote.net/up4/img/panflash00070603.png

追いつかないんだけど
1
10
11
12
13
14
15
16
17
18
19
21,31,41,51,61,71,81,91
100
101
110
111
112
113
114
115
116
117
118
119
120
121

トンチかよ

>>21
１１で2個書くやん

>>47
俺は面白いと思った

>>40
ワロタ。採用！

>>47
＞0からnの間の全ての数を書くのに必要とされる

>>40
おい

これ実際は自然数じゃねーの

>>47

>>43
あー『小さい方から2番目』とか謎の解釈してたorz

まーた、メルカトルってるのかお前ら。
f(13)=6

この時点でグーグルの問題じゃないことぐらいわかるだろ？
彼らは2進数でしか物を考えない。この問題は素人が作ったブラフ。

f(n)<n (n=2,3,4...)の証明がわからん

>>59
f(2)=1である
f(n+1)はf(n)かf(n)+1のどちらかである

以上のことより数学的機能法からnが2以上のときf(n)>nとなる

理系出てるけ質問の意味がわからんｗ

int function()
{
・・・
・・・
・・・
}
return 1;

こういう事？

>>60
>f(n+1)はf(n)かf(n)+1のどちらかである

嘘つくなw

>>60
f(11)=f(10)+2

returnの位置書き間違えたｗ

>>60
f(n)が方程式で表せないと数学的帰納法使えないだろ

>>61
全然違う。それはコンパイラさえ通らない

//こういうこと
int func(int arg)
{
return 1;
}

A.ググれ

誰かちょちょいとプログラム書いて試してみてくれ

Googleに入ったらGoogle以上のものは作れないから。
結果的に失敗して野垂れ死にしたら、そこまでの人だったとして諦めるしかない。

>>66
それ仮引数がどんな数字でも1を返すじゃん

>>61
n = 0
for i in range(x):
　　for c in str(i):
　　　　if c == '1':
　　　　　　n+=1
return n

ｆｆ（11）＝ｆｆ（4＋7）

>>61
int f(int n)
{
　int i, j;
int count;
　char str[100];

　count = 0;
　for (i = 1; i <= n; i++) {
　　sprintf(str, "%d", i);
　　for (j = 0; str[j]; j++) {
　　　if (str[j] == '1')
　　　　count++;
　　}
　}
　return count;
}

googleで調べますん

ググったら答えは199981って書いてありました

しょうもない問題だな

これ、一問だけなら気合でとけるな
法則はわかったし

0〜9：1
10〜99：1*9+10
100〜999：(1*9+10)*9+100
一般化めんどいなこれ

>全ての数を書くのに必要とされる「1」の数
意味分からん
>>47の解釈であってるのか？

(1, 1), (6, 13), (n, n) あとはわかるだろ

>>79
0からnまでの数字を書くときに1が何個必要か

>>66,71,73
わかんねｗ

http://i.imgur.com/VDL9cVV.jpg
http://ideone.com/0myU1T

プログラム回してみたやついる？

細かいことは上手く説明できませんけど、御社に対するやる気は負けません！
どうぞよろしくお願いします！

面接で即答できるやつ変態だろ

ホ〇ダの面接

家族や親類で〇ンダ社員
もしくはホン〇に深くかかわってような仕事をされている方はいますか？

>>82
インデントを全角スペースでやってるから半角に置換しないと実行できない。

誰か教えて欲しいんだけど、これは数Cレベルの問題なの？
真面目に教えてくれ、解けるような人間になりたい

誰か教えて欲しいんだけど、これは数�VCレベルの問題なの？
真面目に教えてくれ、解けるような人間になりたい

そもそも数学の問題ではないと思う
俺文系だけど

>>89
中学レベル

>>91
>>1のいってる意味がわからないんだけど、やばい？

f(0)=0だから・・・

ところで3番目を求めたらいくつになるんだろう

935 ： ノイズw(神奈川県)：2009/09/22(火) 13:39:45.32 ID:zq/qU4mR
　ニュー速は９９％のクズと１％の天才で構成されています

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　100%のクズだった速報
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　http://namidame.2ch.net/news/

学歴的にgoogle入社は不可能だからどうでもいい

>>92
そりゃ解ける以前の問題だからやばいだろ

文字列分解して正規表現でマッチングさせりゃいいじゃん

ダサコードで良いならLONG_MAXからitoaでchar検査すれば良いがそんな奴は採用されない

ｘケタの数の限界（例：x=4のときは1000から9999まで）は

　a(x) = 10^(x-1) + 9* Σa(x-1)　　　←　x>1の時のa(x-1)までの合計の意味でΣ使ってます

だから、人力で解いていけば、nの限界の桁数の予想がつけられる

nがxケタだとすると
a(x) > n > a(x-1)　になるようなxおよびnを求めればいいってことやな

xについての限界は

a(x) >= 10^x　となるxを求めればいい

んじゃないの

そこから
a(x) > n > a(x-1) の条件を満たす二番目に大きいnを割り出していけばよし

ただ、これ、人力だと相当めんどくさいと思うんでけど

二番目に大きいｎなんだから1が正解なんじゃないの？
0より1の方が大きくね

>>92
小難しく書いてるだけで、f(13)=6ってのは、0から13まで書いた時に6個「1」が出てくるよって話
1、10、11、12、13

f(∞)=∞
f(1)=1

∴n=1

このスレ中卒多くてがっかりしたは

3つ目とか存在しないだろ
n>桁数の時点で

よくGoogleが就職したい会社で名前上がるけど会社のことまるで分かってない
世界トップ10の大学入らないと課長より上には行けない
そんでGoogle基準では東大は世界トップ10には入らない

課長までしか日本人に枠無いから一生ヒラだ

>>83
199981ってでた

>>104
そうならないんだなあ、これが
実際に計算すると、どうやら桁数超えそうだな、という傾向が見えてくる
20桁までには限界生きそうな感じ

私が入社した場合こういった問題を解決出来る部下を雇い
私は部下を監視したいと思います

プログラム組んでGoogleパワーで解いてみせろや！

と逆ギレする

最大数だってことを証明しないと

ああすべての数か・・・

「答えは、『 199981 』です。グーグルで検索したので間違いないです。」

n桁の整数を考える、
1の位が1で、他の位が任意の数(0〜9)のとき
10の位が1で、他の位が任意の数(0〜9)のとき
…
nの位が1で他の位が任意の数(0〜9)のとき、使用される1の数が1増える
よってf(10^n-1)=n*10^(n-1)
L.E.D.

0とか1って答えた奴は中卒だな

プログラムもわかんねｗ
http://ideone.com/I479km

プログラム書ける奴なら普通に解けてしまうな

>>1
日本語でおｋ

まず、問題の意味が解らず９５%が脱落だな

1
199981
199982
199983
199984
199985
199986
199987
199988
199989
199990
200000
200001
1599981
1599982
1599983
1599984
1599985
1599986
1599987
1599988
1599989
1599990
2600000
2600001
13199998

プログラムまわしたらこうでた

>>119
これ結果どう見たらいいの？

>>119
なんで連番があるんだ

追いつくんだなこれ
でも最大っていくつだ

>>119
コードプリーズ
まぁ問題の意味もあんまわかってないけどｗ

>>120
これは地道にf(n)=nを満たす数字をリストアップしてったもの
もしこれが限界までやった数字のリストであれば、下から二番目が正解

>>119
いやおかしいだろこれ

すげえｗ
やっぱGoogleすげえよｗ

正解は
2600001

1番大きな数を求めよがそもそも解けないんだが

>>119
「こうでた」じゃねえよｗｗｗ
検算ぐらいしろよカスｗｗｗ

>>121
いや、　なるものはなるでしょ
問題の意味わかってりゃ疑問にならないはず

>>121
f(n)に含まれる1の数が1つで連続のときはf(n)の増加量=nの増加量じゃないの

intで最大ｗｗｗ
longで最大ｗｗｗ
せめて多倍長整数でやれ

これ整数nがいくつまでかを定義しないと
意味ないよね

>>121
最上位の位の1の分だけ増えるだろ

>>133
整数nは整数nだろ

>>133
いや、意味ある

正しく計算すれば、限界があることがわかってくるようになってる

2番目に大きいって、最大値が求められるのか？

>>119
どっかで間違ってるぞこれ

答えは数字じゃないよ
関数で出る

数字が例えば{8,2,6,9}とかあって

1番目に大きい数字：2
2番目に大きい数字：6
3番目に大きい数字：8
4番目に大きい数字：9

じゃないの？

>>89
手作業で解くのは無理
数学とか言うレベルでさえない
プログラマーなら１０分で作れないとヤバイ

ああ、追い越すのか……

いや十分に数学の範疇だから・・・

プログラムでぶん回さなきゃ答えが出ないような問題を口答で即答するグーグル社員パネェ！

これはプログラムで書くの？証明もセット？とりあえず解けたと思うが

f(0) = 0 | f(1) = 1 | f(2) = 1 | f(3) = 1 | f(4) = 1 | f(5) = 1 | f(6) = 1 | f(7) = 1 | f(8) = 1 | f(9) = 1 | f(10) = 2 |
f(11) = 4 | f(12) = 5 | f(13) = 6 | f(14) = 7 | f(15) = 8 | f(16) = 9 | f(17) = 10 | f(18) = 11 | f(19) = 12 | f(20) = 12 |
f(21) = 13 | f(22) = 13 | f(23) = 13 | f(24) = 13 | f(25) = 13 | f(26) = 13 | f(27) = 13 | f(28) = 13 | f(29) = 13 | f(30) = 13 |
f(31) = 14 | f(32) = 14 | f(33) = 14 | f(34) = 14 | f(35) = 14 | f(36) = 14 | f(37) = 14 | f(38) = 14 | f(39) = 14 | f(40) = 14 |
f(41) = 15 | f(42) = 15 | f(43) = 15 | f(44) = 15 | f(45) = 15 | f(46) = 15 | f(47) = 15 | f(48) = 15 | f(49) = 15 | f(50) = 15 |
f(51) = 16 | f(52) = 16 | f(53) = 16 | f(54) = 16 | f(55) = 16 | f(56) = 16 | f(57) = 16 | f(58) = 16 | f(59) = 16 | f(60) = 16 |
f(61) = 17 | f(62) = 17 | f(63) = 17 | f(64) = 17 | f(65) = 17 | f(66) = 17 | f(67) = 17 | f(68) = 17 | f(69) = 17 | f(70) = 17 |
f(71) = 18 | f(72) = 18 | f(73) = 18 | f(74) = 18 | f(75) = 18 | f(76) = 18 | f(77) = 18 | f(78) = 18 | f(79) = 18 | f(80) = 18 |
f(81) = 19 | f(82) = 19 | f(83) = 19 | f(84) = 19 | f(85) = 19 | f(86) = 19 | f(87) = 19 | f(88) = 19 | f(89) = 19 | f(90) = 19 |
f(91) = 20 | f(92) = 20 | f(93) = 20 | f(94) = 20 | f(95) = 20 | f(96) = 20 | f(97) = 20 | f(98) = 20 | f(99) = 20 |

>>105
定年までGoogle正社員の称号が保てるのなら万年ヒラでいいや

シフト操作できれば一発
10進数しか使えないバカかどうか判別する問題
大学情報科の期末試験レベル

こんな中卒レベルの問題で可否問うなら
中卒採用試験でもすればいいんじゃねえの
7年の差はでかいぞ

Twitter 社(米) 採用面接受験記
http://d.hatena.ne.jp/elm200/20110926/1316992422

そもそも問題の意味分かって無い奴多すぎだろ
ネタなのかなんなのか

f(10)=1
f(100)=20
f(1000)=300
f(10000)=4000

>>148
これプログラムじゃなくて筆記の問題じゃないの

f(9)=1
f(99)=9f(9)+10
f(999)=9f(99)+100

f(999)=9^2+9*10+100

9がn個並ぶと
f(9...9)=Σ{k=1→n}9^(n-k)10^(k-1)

>>119
たしかに
f(199981)=199981
なら
f(199982)=199982
だよな
２番目に大きいnってやっぱり問題文がおかしいじゃねーかｗ

はい sprintf使わないやつ
http://pastebin.com/RShEjVsp

f(100) = 21 | f(101) = 23 | f(102) = 24 | f(103) = 25 | f(104) = 26 | f(105) = 27 | f(106) = 28 | f(107) = 29 | f(108) = 30 | f(109) = 31 |
f(110) = 33 | f(111) = 36 | f(112) = 38 | f(113) = 40 | f(114) = 42 | f(115) = 44 | f(116) = 46 | f(117) = 48 | f(118) = 50 | f(119) = 52 |
f(120) = 53 | f(121) = 55 | f(122) = 56 | f(123) = 57 | f(124) = 58 | f(125) = 59 | f(126) = 60 | f(127) = 61 | f(128) = 62 | f(129) = 63 |
f(130) = 64 | f(131) = 66 | f(132) = 67 | f(133) = 68 | f(134) = 69 | f(135) = 70 | f(136) = 71 | f(137) = 72 | f(138) = 73 | f(139) = 74 |
f(140) = 75 | f(141) = 77 | f(142) = 78 | f(143) = 79 | f(144) = 80 | f(145) = 81 | f(146) = 82 | f(147) = 83 | f(148) = 84 | f(149) = 85 |
f(150) = 86 | f(151) = 88 | f(152) = 89 | f(153) = 90 | f(154) = 91 | f(155) = 92 | f(156) = 93 | f(157) = 94 | f(158) = 95 | f(159) = 96 |
f(160) = 97 | f(161) = 99 | f(162) = 100 | f(163) = 101 | f(164) = 102 | f(165) = 103 | f(166) = 104 | f(167) = 105 | f(168) = 106 | f(169) = 107 |
f(170) = 108 | f(171) = 110 | f(172) = 111 | f(173) = 112 | f(174) = 113 | f(175) = 114 | f(176) = 115 | f(177) = 116 | f(178) = 117 | f(179) = 118 |
f(180) = 119 | f(181) = 121 | f(182) = 122 | f(183) = 123 | f(184) = 124 | f(185) = 125 | f(186) = 126 | f(187) = 127 | f(188) = 128 | f(189) = 129 |
f(190) = 130 | f(191) = 132 | f(192) = 133 | f(193) = 134 | f(194) = 135 | f(195) = 136 | f(196) = 137 | f(197) = 138 | f(198) = 139 | f(199) = 140 |

0

>>146
f(11)=4
これって1,10,11の3じゃないの？

f(9)=1
f(99)=10f(9)+10
f(999)=10f(99)+100

f(999)=10^2+10*10+100=

9がn個並ぶと
f(9...9)=Σ{k=1→n}10^(n-1)=100n

>>159
11には1が2つあるじゃん

コード書いて解こうとしてる奴は無限にメモリを持ってるのか？

ちょっかんだと１が最大な気がするなあ。ちょっとやってみるか

確かに馬鹿判別式にはなってるのかもしれんな

n≦20億で調べれば大丈夫なはず

>>152
f(10)=2
f(100)=21
f(1,000)=301
f(10,000)=4,001
f(100,000)=50,001
f(1,000,000)=600,001
f(10,000,000)=7,000,001
f(100,000,000)=80,000,001
f(1,000,000,000)=900,000,001
f(10,000,000,000)=10,000,000,001
じゃね？

問題の意味すら分かってない奴ばっかりでワロタｗｗ

忍法長リセットされちゃった

javascriptでやってみた。
chrome持ってるやつはF12おして、consoleのタブを開いてコピペして実行

var n= 1000;var c = function ( n ) { var r,i; r=0,i=1; while(i++ <= n ){ r += ((i+"").split("1").length-1); } return r }; while (n-- >= 1) { console.log( "f("+n+")="+c(n))}

>>166
はい

f(199980) = 199979
f(199981) = 199981
f(199982) = 199982
f(199983) = 199983
f(199984) = 199984
f(199985) = 199985
f(199986) = 199986
f(199987) = 199987
f(199988) = 199988
f(199989) = 199989

f(999)=300
f(998)=299
f(997)=299
f(996)=299
f(995)=299
f(994)=299
f(993)=299
f(992)=299
f(991)=299
f(990)=299
f(989)=298
f(988)=298

f(13)=6
f(12)=5
f(11)=4
f(10)=3
f(9)=1
f(8)=0
f(7)=0
f(6)=0
f(5)=0
f(4)=0
f(3)=0
f(2)=0
f(1)=0　あれ？
f(0)=0

その場で作ったせいで、バグってるけど
やっぱ1が最大値なきがするな

答えは実数じゃないだろｗ
最大になるnから１個小さいｎが求まる公式だろ

535200001
でいいことにしようw
1111111110
までやったけど、証明の仕方がわからんから、この先はわからんw

せっかく昨日LV10になったばかりだったのに

535200001でええのか？

これってナベアツがバカになる回数求められんじゃね？

>>119
これ間違ってるの？
俺もこうなったんだけど

f(199990)=199991
f(199989)=199989
f(199988)=199988
f(199987)=199987
f(199986)=199986
f(199985)=199985
f(199984)=199984
f(199983)=199983
f(199982)=199982
f(199981)=199981
f(199980)=199980
f(199979)=199978
f(199978)=199977

うお、確かにこの辺にもあるのか。
これ計算で解いたら負け系なのか。

どうやるんだ。

直感だと大きい数字はね〜だろって思うのに、実際は違うんだから面白い

御託はいいからさっさと解答を書けよｗｗｗ

漸化式たった

P(N) ：　N桁の範囲内で必要な1の数
P(N)=10^(N-1)+10*P(N-1)

あってる？

もう解かれてた恥ずかしい

>>169は、i-1でとりあえずバグはなおる

でも、答えてきには、問題が間違ってる気がする。
２番目に小さい値は？で、199981がこたえな気が。

追いつかないと思ったら追いつくのか
111110
111111
111112
こういうところで加速するのね

1111111110の次に、1111111111が来ると
1の数は1111111120になって、本隊を追い越すから
1111111110が最大で間違いないな。
たぶん……

ちょっと待った
いま>>181が良いこと言った

1111111110以降が出ないから535200001が正解ぽいな

nが11桁以下を調べればいいと思うけど、これ以上わからん

f(10^n)=n*10^(n-1)+1

f(10^9)=9*10^8+1 < 10^9
f(10^10)=10^10+1 > 10^10

10^9〜10^10にあるのか？

0からnの間のすべての「整数」を書くのに必要とされる…
って勝手に解釈していいの？

100000000までの結果テキストに出力したら1.8GBになった

特大の釣り師を期待している

>>188
それが答えだとしたらプログラム無しでは厳しいな
最大ならホワイトボードかなんかで答えられそうだけど

ああ2番目に大きいやつか
小さい方から2番目かと勘違いしてたわ

100-1ができれば充分

その1はお前だHAHAHA
終わり

プログラム書いても桁が大きくなると死ぬんだけど
皆どんなプログラム書いてんの

全く意味がわからない
理系はこんなのやってんのか・・・
てか意味あんの？

プログラムの力技しか無理なのかなあ？
でも、逆にプログラムOKなら、その辺のプログラマでも出来て問題の意味が。
そのための1以外なさそうっていうひっかけなのか

┌ Adblock Edge 広告抹消アドオン（Adblockには様々なブラウザ用も存在。Adblock+(Plus)は金で広告を通すので×
├ https://addons.mozilla.org/ja/firefox/addon/adblock-edge/
└┬ Element Hiding Helper （Adblockの追加機能。要素非表示でテキスト広告も抹消
　 └ https://addons.mozilla.org/ja/firefox/addon/elemhidehelper/
┌ Ghostery （トラッキング防止 Googleのアドセンスやアクセス解析カット）[Firefox,chrome,opera,IE
└ http://www.ghostery.com/
┌ RequestPolicy （閲覧サイトから呼び出す外部サイトの遮断・許可、転送警告
└ https://addons.mozilla.org/ja/firefox/addon/requestpolicy/
┌ NoScript （JavaScriptやJavaアプレットの実行、プラグイン起動を制御
└ https://addons.mozilla.org/ja/firefox/addon/noscript/
┌ A Killer Mod （アフィリエイトリンク書換） [Firefox,chrome,opera
├ http://web.archive.org/web/20130227041129/http://www7b.biglobe.ne.jp/~yamj/archives/a_killer_mod/
└┬ Scriptish （Firefoxはこれを先に入れる
　 └ https://addons.mozilla.org/ja/firefox/addon/scriptish/
┌ Internet Explorer 9用 Tracking Protection Lists （IEでアクセス・リスト追加
└ http://ie.microsoft.com/testdrive/browser/p3p/
┌ Iron（ chromeと同じベースの完全互換ブラウザ。GoogleUpdate等カット
└ http://www.srware.net/software_srware_iron_download.php
┌ Microsoft Office IME 2010（無料で使用可能
└ http://www.microsoft.com/ja-jp/office/2010/ime/default.aspx
　　　　　　　　　　　　　　 ／
　　　　　　　　　　　　　 <　　　ﾋﾞﾋﾞﾋﾞ 　|￣￣￣￣￣￣￣￣￣￣￣￣|
　　　　　　　　　　　　　／　　　　　　　 |.ぁゃιぃ接続を感知しました.|
　　　　　　　 ＼_＼_＼ 　 　 　 　 　 　 |＿＿＿＿＿＿＿＿＿＿＿＿|
　　 ＿　　　　　＼ ＼ ＼　 >>1
　 /||__|∧　　 ＿＿|＿＿＿
　（Ｏ´∀｀）　 |　|::::::::::::::::::::::|　　Adblock Plusが控えめな広告として通しているフィルタリスト
　（つ　　 つ／　|::::::::::::::::::::::|　　ttps://easylist-downloads.adblockplus.org/exceptionrules.txt
　／￣￣￣≡....|;;;;;;;;;;;;;;;;;;;;;:|

問題は制限時間だな
どれくらいで解ければいいんだろう

簡単に解ける法則があるんだろ

鳩の巣原理じゃないの？

>>23
かわいそう

>>25
0があるから0-9の間で2つだ
最大が1であることを証明すれば答えは0だ

>>197
int Count(int num){
　int i = 0;
　do{
　　if( (num % 10) == 1)i++;
　}while(num /= 10);
　return i;
}

int f(int num){
　int i, sum = 0;

　for(i=1; i<=num; i++){
　　sum += Count(i);
　　if(sum == i){
　　　printf("%d\n", i);
　　}
　}
　return sum;
}

nにf(n)が追いつかないと思ってたら1111111とかで一気に増えるんだな

>>206
うおお速い
でもこれでも10万ぐらいでだんだん遅くなっていくけど単純にスペック不足か？
億とか調べてる人はどうやってるんだ

>>208
総当たりしてるから、遅くなってるように見えるだけで
次の数になかなか到達しないだけ。
待ってればそのうち出るw

>>209
その次までが1日とかかかりそうなんだけど

>>208
f(n)はf(n-1)の結果を利用して計算すれば大幅に短縮できそうな気がする。

０

ループ前提だから、残化式でとけばよ

>>211
俺はそれでやってる

>>211
なるほど
天才すぎるわ

100000000まで調べても8秒ぐらいだぞ
real 0m8.542s
user 0m8.532s
sys 0m0.000s

mysql

こういう問題をプログラムでやってみることに楽しさを感じる人間はプログラミングを趣味にしよう

>>216
早いな C?

斬化式です！変換できないぐらいのをかっこつけてつこうた
f(n-1)の値に足すよね。って話と同じだよね

最大の証明方法がわからんw

なんでプログラムで解こうとしてる奴がいるんだ？原理的に無理だろ？無限大の整数相手に調べられるとでも思ってんのか？

自分の場合は数学の前にまず国語を勉強し直さなきゃならないって思った・・・>>1の言ってる意味がぜんぜん判らんｗ

億でも2秒ぐらいで出来た
ありがとう

>>162
Googleさんをあまり舐めない方がいいのである

これ問題が間違ってない？
2番目に大きいnじゃなくて2番目に小さいnって言いたかったんじゃないの

　　ワケ　　　　　ワカ　　　　 　 ラン
　 ∧＿∧　　　∧＿∧　　　　∧＿∧
　（　・∀・）　　（　・∀・）　　　（　・∀・）
⊂　⊂　 ）　　（　Ｕ　　つ　　⊂__へ　つ
　<　<　<　　　　）　）　）　　　　　（＿）|
　（＿（＿）　　（_＿）＿）　　　 彡（_＿）

ユニークな難問で知られるGoogleの入社試験について、
同社のシニアバイスプレジデント・Laszlo Bock氏が、
ニューヨーク・タイムズ紙が行ったインタビューのなかで、
効果が「全くなかった」と述べた――という記事が話題を呼んでいる。

http://r25.yahoo.co.jp/fushigi/jikenbo_detail/?id=20130703-00030884-r25

0

おもしれえ
他にもっとこういうプログラムで解く問題ないの

>>220

>>220
ざ・・・漸化式

0〜9で 1は 1個

0〜99で 10の位が1のとき10の位の1が10個、それぞれの10の位につき1の位に1が一個ずつで計10個、合わせて20個

0〜999で 100の位が1のとき100の位の1が100個、それぞれの100の位につき下二桁(10の位と1の位)がそれぞれ20個ずつで計200個、合わせて300個

0〜9999で 1000の位が1のとき1000の位の1が1000個、それぞれの1000の位につき下三桁(100の位と10の位と1の位)がそれぞれ300個ずつで計3000個、合わせて4000個


あとは分かるな？

http://ideone.com/zu0Yvl
書けた書けた
たぶんこれ系のコード書いてあたりつけて計算するのが模範解答じゃないの

>>230
こういうのプログラミングで解くのが好きなやつは「競技プログラミング」で検索
英語だけどTop Coderがオススメ

普通自然数nに0は入らないけどな

>>236
>>1に自然数なんて書いてないぞ

f(9) = 1
f(99) = 20
f(999) = 300
f(9999) = 4000
f(99999) = 50000
f(999999) = 600000
f(9999999) = 7000000
f(99999999) = 80000000
f(999999999) = 900000000
f(9999999999) = 1000000000

何でこうなるんだすげえな

>>219
ちんちんプラプラだよ

>>222

>>113を理解出来れば、上限が有ることが判る。
10の整数乗で表せる数値では、10桁を境にf(n)の値はnを超えて以降増大を続ける。
問題は10の整数乗で表せる数値の間の揺れだが、
桁数が100を超えると仮に次の桁上がりまで１が全く出てこないとしてもf(n)の値はnより小さくならない数値になるので、101桁以上は考慮しないで良い。
たぶん、じっくり考えれば、考慮しなければならない上限はもっと下げられそう。

>>240
10桁で大丈夫だよ

>>240
ごめん適当言った

>>238の規則性と、10桁がポイントなんだろうけど
それをプログラム以外で解く方法ってなんだろう。

>0からnの間の全ての数を書くのに必要とされる「1」の数を返す

これが全然わかんないんだけど

>>244

f(0) → 0 → 0個
f(1) → 0 1 → 1個
f(2) → 0 1 2 → 1個
f(3) → 0 1 2 3 → 1個
f(4) → 0 1 2 3 4 → 1個
f(10) → 0 1 2 3 4 5 6 7 8 9 10 → 2個
f(13) → 0 1 2 3 4 5 6 7 8 9 10 11 12 13 → 6個

>>243
前回桁までの１の数の十倍＋新規の桁の１の数で>>238になる

>>245
えーなにそれ
「書くのに必要とされる」って数学用語があると思った

199981は違うの？

>>248
それは「2番目に小さいn」
問題は「2番目に大きいn」を求めよだから違う

>>238
三桁ごとに区切ってくれ
1の位の「１」の出現率は１０回（０−９）に１回
１０の位の「１」の出現率も１００回に１０回
１の位もその時、１００回に１０回出現してるから、１０＋１０で
ｆ(９９)=２０

なんか目途がつきそうだけど、具体的な数字は手作業じゃぁ厳しそうね

>>249
ソッカー

f(9) = 1
f(99) = 20
f(999) = 300
f(9,999) = 4,000
f(99,999) = 50,000
f(999,999) = 600,000
f(9,999,999) = 7,000,000
f(99,999,999) = 80,000,000
f(999,999,999) = 900,000,000
f(9,999,999,999) = 10,000,000,000

>>238
これ１０桁目の右辺のｎ、０が一つ少ないんじゃね？

これ分かったら俺もゴーグル入れるの？

>>233と>>238で1からある程度まではf(n)<nだけど
途中からf(n)の増加が大きくなって1点で一致した後にf(n)>nになるからな
その一点が整数かどうかを調べたら終わりだ

>>253
>>252が正しい

>>255
途中で抜きつ抜かれつみたいになるから
そう簡単でもなくね

関数があるんだったら手作業で調べる必要ねえだろ

f(n)の規則性を見つけて
10桁超えるとf(n)がnを超えるのは
なんとなくたどりつけそうだけど

そこから同値の２番目って結構無理げーじゃね。

プログラムあり気なのかな。

K桁の整数で最上位が1の数をNとする
NのK-1桁以下の数をMとする
(例 N=13671 なら K=5 M=3671)
f(N) = M + f(M) + f(10^K) - 1
と書ける

>>256
じゃぁ、百桁超えたら、抜きつ抜かれつがなくなるかな

でもこの位ひねらないと、
公式と過去問にあてはめれば溶けちゃうような
感官同率レベルの自分が頭がいいと勘違いしているおばかさんとか
たくさんきちゃうんだろうな

>>256
抜きつ抜かれつになる範囲はかなり狭いことはすぐに想像できないと

＞たとえば、『f(13)=6』になります
よくわかんねえんだけど
1、10、11、12、13
なんで6なん？

>>259間違えた

K桁(K>1)の整数で最上位が1の数をNとする
NのK-1桁以下の数をMとする
(例 N=13671 なら K=5 M=3671)
f(N) = M + f(M) + f((10^(K - 1)) - 1)
と書ける

>>233は
f((10^(K - 1)) - 1) = f(10^(K - 1)) - 1 = (K - 1) * (10^(K - 2))

>>263
1が6個出てきてるじゃない

>>263
＞1、10、11、12、13

これをレスするときキーボードの１のキーを何回押したか考えろ

>>265
ほんとださんくす

学校の試験じゃないんだから正解はどうでもいいんじゃないの

解への導き方、ユニークさ、あきらめずに挑戦した姿勢とかが
見られてるってとこに気付くのが正解じゃないのか

０

これはコードを書くのではなく咄嗟に筋道立てて論じれるかどうかを見るんだろう
コーダーばかり集めた結果会議の途中でデータが必要になった時に
いきなりコードを書く奴が出てきて会議がダレるのが嫌になったんだろう

>>259
桁さえ分かってしまえば
あとは交点出すだけでしょ？
N桁の時から1桁ずつ増やしていけばよくて
その桁の算出式も出てるわけだから単純作業でもうでるよ

間違えた>>258だった恥ずかしい

ていうか>>1のソースはどこよ

そろそろ誰か完璧で分かりやすい解答を
一つのレスに書いてよ
安価とか使わずに

1:1回
10:2回
11:4回
111:36回
11111111:8888896回
111111111:100000008回

どうやら、無限大に近い値みたい。
0を入力したら、ちゃんと0を返すことまで確認済み。

g(x)= 1 (1≦x≦2)
　　　0 (0≦x<1,2≦x<10)
かつ
g(x)=g(x+10)
を満たす周期関数とする。すると

f(n)=∫{0〜n+1}(g(x)+g(x/10)+g(x/100)+…)dx
と書ける。

単純に99までは「1の位10回」と「10の位が1の時10回」
999までは「1の位100回」と「10の位が1の時が10回が10回」と「100の位が1の時100回」
この流れでいくと10桁の時だから「999999991」じゃないか？

>>261
流石に早慶関関同立マーチあたりのバカ私大は書類で切られるんじゃね？

>>277
違った

K桁(K>1)の整数で最上位が1の数をNとする
NのK-1桁以下の数をMとする (例 N=13671 なら K=5 M=3671)
f(N) = M + f(M) + f((10^(K - 1)) - 1) ... [A]
N = M + (10^(K - 1)) ... [B]
と書ける
f((10^(K - 1)) - 1) = f(10^(K - 1)) - 1 = (K - 1) * (10^(K - 2)) ... [C]
[A]に[C]を代入
M + f(M) + f((10^(K-1)) - 1) = M + f(M) + (K - 1) * (10^(K - 2))
f(N) = N は
M + f(M) + (K - 1) * (10^(K - 2)) = M + (10^(K - 1))
M + f(M) + (K - 1) * (10^(K - 2)) = M + 10 * (10^(K - 2))
f(M) = (10 - (K - 1)) * (10^(K - 2))
f(M) = (11 - K) * (10^(K - 2)) ... [D]
K桁(K>1)の整数で最上位が2〜9になる数をPとし
また、整数Pの最上位の数(2〜9)をQとし、PのK-1桁以下の数をRとし
S = (10^(K - 1)) + ((10^(K - 1)) - 1) = (2 * (10^(K - 1))) - 1 ... [E] と定義する (例 P=37891 なら K=5 Q=3 R=7891 S=19999)
f(P) = f(R) + f(S) + (Q - 2) * f((10^(K - 1)) - 1) ... [F]
P = R + Q * (10^(K - 1)) ... [G]
と書ける
なお、Sは最上位が1なのでf(S)は[A]のように展開できる
SのK-1桁以下の数は(10^(K - 1)) - 1 になるので
f(S) = ((10^(K - 1)) - 1) + f((10^(K - 1)) - 1) + f((10^(K - 1)) - 1)
= ((10^(K - 1)) - 1) + 2 * f((10^(K - 1)) - 1) ... [H]
になるので[F]は
f(P) = f(R) + ((10^(K - 1)) - 1) + Q * f((10^(K - 1)) - 1) ... [I]
となる、f(P) = P は
f(R) + ((10^(K - 1)) - 1) + Q * f((10^(K - 1)) - 1) = R + Q * (10^(K - 1))
f(R) = R - (Q - 1) * (10^(K - 1)) - 1 - Q * f((10^(K - 1)) - 1) ... [J]
だめだ、ぐちゃぐちゃしてきて混乱してきた

一番大きいのは「10000000001」な気がする

f(9999999999)=10000000000
f(10000000000)=10000000001
なんだなこれが
惜しいけどこの辺は一致しない
そして多分、ここが上限

>>281
ｆ(10000000000)=10000000001
ｆ(10000000001)=10000000003

>>281
これも違った

f(10^n)=n･10^(n-1) +1

答えは、９９桁代と予想

とりま中間報告
111111111から200000000までで f(n)=n に該当する値は１件
117463825みたい
ソースほしい人は言ってね。なれないC#&amp;突貫工事でかなり見づらいけど
検証手伝ってほしいです。

何でC#で書くん？

>>287
117463825
まじだった

全くついていけない

X=1〜9として、

f(X999)=(X99+1)+10(X9+1)+100(X+1+f(X))

間違えた。

X=1〜9として、

f(X999)=(X99+1)+10(X9+1)+100(X+1)+1000(f(X))
ｎ桁でも同じ

　　　　　　　　　　　　　 　 /i　　　 　　　　　　　　　　　　　
　　　　　　　　　　　　 　 /　i　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　/　　i　　　　　　　　　　　　　　　
　　　　　　　　 　 　 　/　　　i 　　　　　　　　　　　　　
.　 　 　 　　 　　　,-‐'　　　 　` 、 　　　　　　　　 　 　
　　　　　　 　　／　　　茨城　　ヽ　　　　　 　　　 　
　　ｷﾘｯ 　　　,'　　___　　　　　　　',　　　　　　
　　 　 　 　　/ 　ｨ=rｭ ゝソ　 r:::..ヾi　　　
　　 　　 　／　　　　　 ..::　 / :rｭ､/　　　
　　　 　 　ヽ,　 　　 　　　 /　 　 / 　　＜ユニバーサルメルカトル図法
　　　　　 　/i　　　 　_..__/ ､　　,'ﾉ 　　　
　　　　 　 /　i　　　　ﾞ､⌒ﾞ^;　 /　　　
　　　　 ／_　 ＼　 　　 ￣　 ./　　　　
　　　／i.:::: `ー ､＼ _.:::...._ ／　　　　　　　　　　　　　　　　ｽｹﾞｴ！　　　　ﾏｼﾞｶﾖ　　　　ｶｯｺﾖｽｷﾞ
__,-"/ /:::::...　 　 ｀ヽ`ー‐"ノヽ　　　　　　　　　　　　　　　 ＼　　／　　　 ＼　　／　　＼　　／
　　　　　　　　　　　i　 /￣　　ヽ

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 バカ
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 http://hayabusa3.2ch.net/news/

あれ、もしかして

f(XYZ)=(XY+1)+10(X+1)+100？？

N=A･10^n+B (1≦A≦9　0≦B＜10^n)とおくと
A=1のとき
f(N)=A･n･10^(n-1) + f(B) + (B+1)
A≠1のとき
f(N)=A･n･10^(n-1) + f(B) + 10^n
ってでたけど

さっぱりわからない

>>288
そんな事言われても・・・
好奇心からとしかいえないです。。

>>289
ふおおサンクス
でももう５億まで行ってるのかよー。。

ちなみに
200000000 - 400000000 なし
535200001：○
1111111110：○
でした

スーパーエリートのお前らに聞きたいだけど「折る/折れる」の名詞ってなに？
骨なら骨折と言えるけど歯とか木材とかどんな単語にも幅広く通用する表現を一語でなんと言うんでしょうか

一般式作ったった
一番大きい桁の数字が1でないときと1のときで分ける
何桁でも対応可能だと思うがとりあえず6桁と7桁で
n=２００,００１のとき、
f(n)=(２*50,000+100,000)+0+0+0+0+0+1=100,000+100,000
n=２,６００,００１のとき、
f(n)=(２*600,000+1,000,000)+(６*50,000+100,000)+0+0+0+0+1=2,200,000+400,000+1=2,600,001

n=１９９,９８１のとき、
f(n)=(１*50,000+99982)+(９*4,000+10,000)+(９*300+1,000)+(９*20+100)+(８*1+10)+1=199,981
n=１,５９９,９８１のとき、
f(n)=(１*600,000+599,982)+(５*50,000+100,000)+(９*4,000+10,000)+(９*300+1,000)+(９*20+100)+(８*1+10)+1=1,599,981

おまえら、その前に
>>1の問題はどこから出てきた？Googleと関係あるの？

筆算で出したが「1011319998」でどうだ？

俺も出来た。本質的に同じっぽいな

先頭が1でないとき
f(ABCD)=(ABC+1)+10(AB+1)+100(A+1)+1000

先頭が1のとき
f(ABCD)=(ABC+1)+10(AB+1)+100(A+1)+(BCD+1)

N=A･10^n+B (1≦A≦9　0≦B＜10^n)とおくと
A=1のとき
f(N)=A･n･10^(n-1) + f(B) + (B+1)
A≠1のとき
f(N)=A･n･10^(n-1) + f(B) + 10^n

が正しいとすると
n≧100のとき
f(N)≧A･n･10^(n-1)≧10^(n+1)＞N
だから解の個数は有限

ここから全然進まんｗ
http://i.imgur.com/veRIjvW.png

なんか
世界最大の素数を探せ
ってスレ作ったら、ここの住人が見つけてくれそうな勢いだなｗ

嫌儲のみんなってすごく賢いのね

n＞20のとき
f(N)≧A･n･10^(n-1)＞2A･10^n≧(A+1)･10^n≧N
だから10^21まで調べられれば

公式アップデート
nの桁数を4とすると、

A＞1のとき
f(ABCD)=3(A00)+2(B0)+C+1111

A＝1のとき
f(ABCD)=3(A00)+2(B0)+C+112+BCD

n>4でも成り立つ似たような式が成り立つ。

A＞1のときf(ABCD)の各桁数をWXYZと書くと
Z=1+C
になる。だから、A＞１に解は無い。

n≧20のとき
f(N)≧A･n･10^(n-1)≧2A･10^n≧(A+1)･10^n=A･10^n + 10^n＞A･10^n + B=N
だから10^20まで調べられれば

n≧11だと
f(10^n-1)=n*10^(n-1)≧11*10^(n-1)=10^n+10^(n-1)＞10^n-1
だから、10桁までを調べたらいいね

f(10^10-1)=f(9999999999)=10*10^9=1000000000
から下ったほうが早いのかな

>>40
俺もこれだと思ったけどちがうのか？

>>310
fは増えない場合もあるからその論法はまずいかも

あ、問題見間違えてた・・・

ゴミ文系には分かりません。
すみません。

>>311
おそらく>>1の問題の意図は、1の次にf(n)=nが成り立つnを求めよってことだと思うよ
日本語がおかしくて、思わぬ方向にスレが進んでるけど

原文がこれだからな
"Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?"

>>312
確かにそうだな
面倒くせえなこの問題

整数nが与えられたとき
この時点で意味が分からん
誰に対して与えられたんだ？

なんで急にfがでてきたんだよう

>>298
折損かな。破断、破損は折れるていう意味がなくなっちゃうし。
あるのかな。

スレ立って最初２分で解は０と１だけと思ったが違ったのかｗｗｗ

グーグルは入れないわ

この問題をどうやって作ったのかが気になる

>>317
関数に対してでしょ。

>>287
C＃のコード頂戴

Ｎがn桁まであったとして、各桁の数を[Ni]と書くと、
f([N1][N2][N3][N4]…[Nn])=[N1][N2][N3][N4]…[Nn]
一方で公式から、最上位が１で、最下桁が０＞１のとき、
f(N1N2N3N4…Nn)=(n-1)[N1]*10^(n-2)+(n-2)[N2]*10^(n-3)+…+([N2][N3][N4]…[Nn])+11…12
各桁の公式は次の通り、

最下桁：　[Nn]=2+[Nn-1]+[Nn] (mod10)
ｋ桁目：　[Nn-k]=1+k[Nn-k-1]+[Nn-k]+(繰り上がり) (mod10)
最上桁：　[N1]=1

ｋ桁目と最上位桁が一致したときにやめる事ができる。

まず、最下桁をみると、[Nn]は決まらないが、
１桁目は
　　0=2+[Nn-1] (mod10) →　[Nn-1]=8
２桁目は 0=1+2*[Nn-2]+1(繰り上がり) (mod10)→[Nn-2]=4,9
３桁目は
　　4の場合、0=1+3*[Nn-3]+1(繰り上がり) (mod10)は解なし
　　9の場合、0=1+3*[Nn-3]+2(繰り上がり) (mod10)は、[Nn-3]=9
４桁目は
　　0=1+4*[Nn-4]+3(繰り上がり) (mod10)なので、[Nn-4]=4,9
５桁目は
　　4の場合、0=1+5*[Nn-5]+2(繰り上がり) (mod10)で解なし
　　9の場合、0=1+5*[Nn-5]+4(繰り上がり) (mod10)なので、[Nn-5]=1,3,5,7,9

ここで１が出てきたので、やめる。n-5=1つまり、nは６桁が最小。
最小桁は任意なので1が最小、結局
N=199981
が答えとなる。

>>323
それならなんでそう書かないの？
問題が説明不足じゃん

あ　俺底辺高卒なんで適当に流してください

>>326
書いてあるよ。「関数が」って。

>>325
各桁が１以上のときだわスマソ

>>327
しゃしゃってすみませんでした
俺底辺高卒で日本語もあまり得意じゃないんで適当に流してくれたら幸いです

有限解ではあるな
手計算じゃどうやってもむりぽだな

グーグルの試験でC#なんて使っていいと思ってんのか

>>325
公式当たってる？
例えばn=116のときどうなる？

18446744073709551615←unsigned long long int
100000000000000000000←10＾20

これさー10＾20まで調べればいいってレスあるけど
１桁足りなくね？

>>324
どうぞー（まだ不完全ですが。。）
http://kie.nu/18VR
ダウンロード用パス：535200001

>>332
ご指摘ありがとう。各桁にもう少し強い条件が要りそう

>>333
18446744073709551615=1.8…×10^19<10^20だけど…

数学板の奴らならこれ解けるのかな？

指定範囲検索のバグをつぶしておきました。
http://kie.nu/18Wu
ダウンロードパスはさっきと同じです。
寝、寝ますよ〜寝る寝る・・・ ヌッ！（卒倒）

>>334
サンクス
見てみたけどやった事ないからC＃はやっぱわからん

>>336
18446744073709551616〜10＾20までの数はいいのかい？

>>319
そんな日本語がったのか
サンクス

まぁ回しとくわｗ
http://i.imgur.com/bP3JfsO.png

>>1
ソースなし糞スレ

↓でやれ

数学
http://uni.2ch.net/math/

>>339
>>336は>>333が桁数足りない…って指摘に対する返答ってだけで
18446744073709551615から10^20の間に満たすものがあるかどうかは分からない

rubyみたいに大きな数扱える言語で回してみたら？

a

Cで作ったぞ

ぶっちゃけこれ総当たりプログラムで解いて答えが正解でも意味ないだろ
問題の趣旨と違うし

Cで作ったぞ
Cかじったばっかりだから間違いがあったら言ってくれ

#include <stdio.h>
int count(int n){
int i=0;
while(1){ if (n % 10 == 1) { i++; }
if (n == 0) { break; }
n = n / 10; }
return i;}


int main(void)
{
int i;
int sum = 0;
for (i = 1; i < 100000000; i++) { sum = sum + count(i);
if (sum == i) { printf("f(%d)=%d\n",i,i); } }
return 0; }
117463825とか出てきてワロタ

ソース書き換えて今調べてる数をDOS窓に
f(n)=nとなる数字をtxtファイルに
出力するよう書き直して走らせてたけど駄目だこれ

時間かかりすぎるわ
お前ら後は頼むんだ
http://i.imgur.com/sUC0vZd.png

>>348
117463825なんて甘い
1111111110を最後に全然出ない

今1111111110まで行ったけど固まった・・・・

ちゃんと並列処理するプログラム書けよ−

-1323939513って出てきたからintじゃだめなんだな書きなおすのめんどくせ

>>353
Cならunsigned int64_tが上限だよ
64bitマシンならgccで__uint128_tまでできるけど

>>351
たぶん固まってない。
数値の上限までは次を探して計算し続ける。
最大値があるなら、それの証明が先。
証明できないと終了条件が設定できない。
設問が大きい方から二番目だから、最大値はあるんだろう。
さんすうはかせはいないのか？

fって何

>>356
functionの頭文字

で、1が最大だと証明できたのか？

いや最大じゃないよ

答えは535200001です。

http://www.primepuzzles.net/puzzles/puzz_200.htm

答え：ググれカス

よかった合ってたんだな

10進数前提で整数を語っていたことにびっくりだ。

0 1 199981 199982 199983 199984 199985 199986 199987 199988 199989 199990
200000 200001 1599981 1599982 1599983 1599984 1599985 1599986 1599987 1599988
1599989 1599990 2600000 2600001 13199998 35000000 35000001 35199981 35199982 35199983
35199984 35199985 35199986 35199987 35199988 35199989 35199990 35200000 35200001 117463825
500000000 500000001 500199981 500199982 500199983 500199984 500199985 500199986
500199987 500199988 500199989 500199990 500200000 500200001 501599981 501599982 501599983
501599984 501599985 501599986 501599987 501599988 501599989 501599990 502600000 502600001
513199998 535000000 535000001 535199981 535199982 535199983 535199984 535199985 535199986
535199987 535199988 535199989 535199990 535200000 535200001 ここで強制中断

'Visual Basic 6.0
Private Sub Command1_Click()
Dim n&, i&, j&, l&, s$
n = 0
For i = 0 To &H7FFFFFFF
s = CStr(i)
l = Len(s)
For j = 1 To l
If Mid$(s, j, 1) = "1" Then
n = n + 1&
End If
Next j
If i = n Then
Debug.Print i
End If
Next i
End Sub

>>1の日本語がおかしい希ガス
1が出てきた回数カウントするプログラムか何かだと思ったわｗ

>>365
日本語はおかしくないし、「1が出てきた回数カウントするプログラム」と考えても支障はないが？

>>315が原文なら”整数”とは書かれてないんじゃねの

ユニバーサルメルカトル速報

f(4999999999999999999)=10000000000000000000
だった

>>1
直感だけど160ぐらい？

やっべ恥ずかしい

11桁目以降はn=f(n)とはならないな
11桁目以降は、その桁の最初の最高位が1だからそれが効いて、nはf(n)に追いつけないことが示せる
まあ1111111110が最高で間違いないだろうな

どいつもこいつも底辺プログラマーだな
わかり易く例えるなら、

「数字の1を使って答えが100になる式を作れ」
という問題に対し
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+.....=100

という式を作ってるようなもの
まさに底辺だわ

>>373
正解の値とその証明早よ

111-11=100 や (11-1)*(11-1)=100 といった発想が出来ない奴ばかり
ここまで読んでみたが、ただひたすらループで回すコードしかない
お前らみたいな底辺とは絶対に一緒に仕事したくないね

>>329
google「あなた合格です！」

>>364
ほぼ正解と言って良いが、
最初に0が入ってる時点でGoogleに切られるぞ

あと後半で500000000とか、1入ってないよ

7セグメントのことじゃないのか？
俺は「4」だと思う

>>377
ヒント：0もf(n)=nを満たす

7セグだと１が二画になってしまうのか・・

>>380
あそーか
じゃ正解は1か

誰かグラフ作ってよ。

Q. 神はいると思う？　　　　　　　　　
　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　
　いない┐　　　┌───わからない
　　　　 　│ _..-ｰ''''''l'''''― ..、
　　　　　.／ 　 .ｌ,　　|　　　　 ｀''-、
　　　.／　　　　 .ｌ　 .|　　　　　　　＼
　　 /ゝ､　　　　　ｌ.　|　　　　　　　　 ヽ
　 ./　　 .｀'-､　 　 ｌ. |　　　　　　 　 　 ｌ
　│　　　　　 ﾞ''-､ .ｌ,|　　 　 　 　 　 　 l
　 |　　　　　　　　 ｀'″ 　　　　　　　　 |
　│　　　　　　2ちゃんねるで見た 　,!
　　ｌ　　　　　　　　　　　　　 　　 　　 ./
　　.ヽ　　　　　　　　　　　　　　　 　 /
　　　.＼　　　　　　　　　　　　　　／
　　　　 ｀'-､　 　 　 　 　 　 　 ／
　　　　　　　｀''ｰ　..........　-‐'″

setup.exeうぜえええええええええええええええええええええ

>>367
whole number = 整数

>>375
ループで回さないコードでもいいから早よ

触るなよ

>>375
一緒に仕事したくなるような、解答期待してるよ

はいここまできたけど


f(n)= f(s*10^k+t)
=10^k+s*f(10^k-1)+f(t) s>1
=t+f(10^k-1)+f(t) s=1

f(10^k-1)=10^(k-1)+10*f(10^(k-1)-1)
f(10^k-1)/10^(k-1)=f(10^(k-1)-1)/10^(k-2)+1
f(10^k-1)=10^(k-1)*(1+(k-1))=k*10^(k-1)k>1

1の日本語訳が派手に間違ってるのに
答えなんて出る訳ねーだろ

これだから理系は

グラフ
http://i.imgur.com/AHo77l9.gif

>>392
でもこれ
1,111,111の並びで跳ね上がるよね？

111,111の並びでfが跳ね上がったように。

結局解けなかった。悔いが残るのう。

>>252
これ見る限り、答えは9桁以上10桁未満だと思うんだが、

というか
1,000,000の桁では先頭の1がある限り、nとfの伸び率は最低でも同じ
1,000,001で1縮まるし
1,100,000〜1,199,999で少なくとも99,999は縮まる。

f(0)=0
f(1)=1
∴n=1

>>252
g(n)=n-f(n)として
n=9,999,999,999の時は、g＜0なんだな

そこまでも何回も抜きつ抜かれつしているんだろうけど、9999・・・の並びで抜かれるのは初めてか。

>>252
これの様子（規則性）をもうちょっと分かりやすく見るために
もう5ケタくらい進めたうえで
両対数グラフにプロットしたいな

発散スピード違うくね


[n > 0]: f(10^n) = (n * (10^(n - 1))) + 1
n = 1: f(10) = 1 + 1
n = 2: f(100) = 20 + 1
n = 3: f(1k) = 300 + 1
n = 4: f(10k) = 4k + 1
n = 5: f(100k) = 50k + 1
n = 6: f(1M) = 600k + 1
n = 7: f(10M) = 7M + 1
n = 8: f(100M) = 80M + 1
n = 9: f(1G) = 900M + 1
n = 10: f(10G) = 10G + 1
n = 11: f(100G) = 110G + 1
n = 12: f(1T) = 1.2T + 1
n = 13: f(10T) = 13T + 1
n = 14: f(100T) = 140T + 1
n = 15: f(1P) = 1.5P + 1
n = 16: f(10P) = 16P + 1

11 名前：番組の途中ですがアフィサイトへの転載は禁止です[] 投稿日：2013/07/14(日) 13:58:20.05 ID:7k5fSuEs0 [1/3]
>>1
この整数問題糞簡単だな
証明なしでいいならいくつかのパターンを実験してれば答えでてくるんじゃないの？

36 名前：番組の途中ですがアフィサイトへの転載は禁止です[] 投稿日：2013/07/14(日) 14:06:29.06 ID:7k5fSuEs0 [2/3]
f(n)=nってなるのがn=1しかないんだが？
肝となるnだけ抜粋して書き出していったんだが、n=100でf=21
以降fがnの増え方よりも速度をあげて増える機会は、111や、121、131、211、311、1111くらいしかない

到底f=nとはなりえないんだが

[n > 0]: f(10^n) = (n * (10^(n - 1))) + 1
n = 1: f(10) = 1 + 1
n = 2: f(100) = 20 + 1
n = 3: f(1k) = 300 + 1
n = 4: f(10k) = 4k + 1
n = 5: f(100k) = 50k + 1
n = 6: f(1M) = 600k + 1
n = 7: f(10M) = 7M + 1
n = 8: f(100M) = 80M + 1
n = 9: f(1G) = 900M + 1
n = 10: f(10G) = 10G + 1
n = 11: f(100G) = 110G + 1
n = 12: f(1T) = 1.2T + 1
n = 13: f(10T) = 13T + 1
n = 14: f(100T) = 140T + 1
n = 15: f(1P) = 1.5P + 1
n = 16: f(10P) = 16P + 1


↑たとえばn=15とn=16だが
1P〜10Pの間でfが1.5P〜16Pに上がっていくからこの間に一致する箇所がある可能性があるし
つまり右側(fの値)が引数の10倍以上になった時点で超えられない値になるはず
つまりn=100が限界

15 名前：番組の途中ですがアフィサイトへの転載は禁止です[sage] 投稿日：2013/07/14(日) 14:00:07.51 ID:mt8XS3Cq0 [1/4]
感覚的にｎは100以下だろ。
後は全部列挙すりゃ終わりだろ。

37 名前：番組の途中ですがアフィサイトへの転載は禁止です[] 投稿日：2013/07/14(日) 14:06:32.19 ID:FYzxTXgu0 [1/3]
n=1しか解が無い事を簡単に証明できるけど

104 名前：番組の途中ですがアフィサイトへの転載は禁止です[] 投稿日：2013/07/14(日) 14:52:26.26 ID:qdecqtVw0 [1/3]
3つ目とか存在しないだろ
n>桁数の時点で

nを使うと問題のf(n)=nと被るからpに書き換えた

[p > 0]: f(10^p) = (p * (10^(p - 1))) + 1
p = 1: f(10) = 1 + 1
p = 2: f(100) = 20 + 1
p = 3: f(1k) = 300 + 1
p = 4: f(10k) = 4k + 1
p = 5: f(100k) = 50k + 1
p = 6: f(1M) = 600k + 1
p = 7: f(10M) = 7M + 1
p = 8: f(100M) = 80M + 1
p = 9: f(1G) = 900M + 1
p = 10: f(10G) = 10G + 1
p = 11: f(100G) = 110G + 1
p = 12: f(1T) = 1.2T + 1
p = 13: f(10T) = 13T + 1
p = 14: f(100T) = 140T + 1
p = 15: f(1P) = 1.5P + 1
p = 16: f(10P) = 16P + 1


↑たとえばp=15とp=16だが
1P〜10Pの間でfが1.5P〜16Pに上がっていくからこの間に一致する箇所がある可能性があるし
つまり右側(fの値)が引数の10倍以上になった時点で超えられない値になるはず


p = 100: f(10^100) = 100 * 10^99 + 1 = 10^101 + 1 となるから、これ以降は一致するf(n)=nは存在しない
p = 101: f(10^101) = 101 * 10^100 + 1 > 100 * 10^100 + 1 = 10^102 + 1

つまりf(n)=nの最大のnは10の100乗未満に存在する

直感的に各桁で1の現れる頻度が0.1なんだから
10桁ないしは11桁でいいだろ

>>24
そら大学なんてコネ作りに行く場所ですし
一流企業入るならコネ無きゃね…

小２で算数挫折したから何言ってるか分からん

f(n)をnの10進表記の下位桁から再帰的に計算するアルゴリズムを考えて
プログラミング言語Schemeのフリーな国産処理系Gaucheで走らせてみたら
数の大きさではなく数の桁数（＝対数）に比例するだけあって
インタプリタでもかなり高速に計算できた．

f(3141592653589793238462643383の10乗)の計算結果

gosh> (count-1 (expt 3141592653589793238462643383 10))

25766322826665858531278093126232570537183322577319848239811
14192607566497483303197283292157110456016938666151493587343
63147462602257465237480922416820548658717312245184480775600
07820590261665750038918020807179044626772404179552198740082
14931337071353191551859288552907397570395

Pentium M 1.73HGz でもこれが一瞬で出る
ただ，たとえばこの数をスタート地点にして，数を一つづつ増やしながら
登場する"1"の個数をどんどん足していって条件を満たす数を探そうとすると
たとえば上の数から＋10000の範囲まで調べつくすのに10秒ぐらいかかっちゃう

>>391

>>409
何、もしかして茨城県民？

>>404
上がり方をもう少し細かく見れば10^10以下を調べればいいってわかる
例えばn=1Pのとき
f(1P)からf(10P)までの上がり方を見ると
f(1P)=1.5P+1
f(2P)=1.5P+15*10^14+10^15+1=4P+1
f(3P)=3.5P+15*10^14+1=5.5P+1
f(4P)=7P+1
f(5P)=8.5P+1
f(6P)=10P+1
f(7P)=11.5P+1
f(8P)=13P+1
f(9P)=14.5P+1
f(10P)=16P+1
で、f(1P)とf(2P)の間は必ずどの数を記述するのに1を使うから、この間、nがf(n)を追い越すことはない
この後もn+1<f(nP)となるからn<f(n)

>>412
おお本当だ
f(n)=nの最大は10G未満確定なんだね

結局これどこの問題なの？

じゃあ最大を探すなら
n=10Gから降順で探せば早いんじゃないのか
f(10G) = 10G + 1 って分かるんだし

f(2P)〜f(9P)の後ろの+1いらなかったな
あとf(3P)=3.5P+〜じゃなくてf(3P)=4P+〜だった

>>416
合ってるんじゃないの？

f(1P) = 1.5P + 1
f(2P) = f(1P) + 1P + f(1P - 1)
　= f(1P) + 1P + (f(1P) - 1)
　= 1.5P + 1 + 1P + (1.5P + 1 - 1)
　= 4P + 1
f(3P) = f(2P) + f(1P - 1) = 5.5P + 1
f(4P) = f(3P) + f(1P - 1) = 7P + 1
f(5P) = f(4P) + f(1P - 1) = 8.5P + 1
f(6P) = f(5P) + f(1P - 1) = 10P + 1
f(7P) = f(6P) + f(1P - 1) = 11.5P + 1
f(8P) = f(7P) + f(1P - 1) = 13P + 1
f(9P) = f(8P) + f(1P - 1) = 14.5P + 1
f(10P) = f(9P) + f(1P - 1) = 16P + 1

気づいたｗ >>417は間違いだったｗ　たしかに+1はいらない

f(1P) = 1.5P + 1
f(2P) = f(1P) + (1P - 1) + f(1P - 1)
　= f(1P) + (1P - 1) + (f(1P) - 1)
　= 1.5P + 1 + (1P - 1) + (1.5P + 1 - 1)
　= 4P
f(3P) = f(2P) + f(1P - 1) = 5.5P
f(4P) = f(3P) + f(1P - 1) = 7P
f(5P) = f(4P) + f(1P - 1) = 8.5P
f(6P) = f(5P) + f(1P - 1) = 10P
f(7P) = f(6P) + f(1P - 1) = 11.5P
f(8P) = f(7P) + f(1P - 1) = 13P
f(9P) = f(8P) + f(1P - 1) = 14.5P
f(10P) = f(9P) + f(1P - 1) = 16P + 1

>>418
最後の式間違えたｗ

f(10P) = f(9P) + f(1P - 1) + 1= 16P + 1

>>418を定式化してみた

[p > 0]:
f(10^p)
　= p * (10^(p - 1)) + 1

[p > 0]:
f(2 * (10^p))
　= f(10^p) + ((10^p) - 1) + f((10^p) - 1)
　= 2 * f(10^p) + (10^p) - 2
　= 2 * (p * (10^(p - 1)) + 1) + (10^p) - 2
　= 2 * p * (10^(p - 1)) + (10^p)
　= 2 * p * (10^(p - 1)) + 10 * (10^(p - 1))
　= (2 * p + 10) * (10^(p - 1))

[p > 0, 3 <= k <= 9]:
f(k * (10^p))
　= f((k - 1) * (10^p)) + f((10^p) - 1)
　= f(2 * (10^p)) + (k - 2) * f((10^p) - 1)
　= f(2 * (10^p)) + (k - 2) * (f(10^p) - 1)
　= f(2 * (10^p)) + (k - 2) * f(10^p) - (k - 2)
　= (2 * f(10^p) + (10^p) - 2) + (k - 2) * f(10^p) - (k - 2)
　= k * f(10^p) + (10^p) - k
　= k * (p * (10^(p - 1)) + 1) + (10^p) - k
　= (k * p * (10^(p - 1)) + k) + (10^p) - k
　= k * p * (10^(p - 1)) + (10^p)
　= k * p * (10^(p - 1)) + 10 * (10^(p - 1))
　= (k * p + 10) * (10^(p - 1))

>>411
ユニバーサルメルカトルじゃないよｗ
たとえば10進表記で [A][B][C][D] という4桁の数までの f の値が計算済みで
そこから頭にXを付けた５桁の数f([X][A][B][C][D])を計算したいとする．

頭に [1] をつけた [1][A][B][C][D] の場合，f の値 f( [1][A][B][C][D]) は
「0, 1, ... , 99, 100, 101, ... , ABCD, ABCD+1, ... , 9999,
10000, 10001, ... , [1]ABCD -1 , [1]ABCDまでに登場する1の個数」
になる（0 も f(0) = 0 で入れちゃってる）．

これを「0, 1, ... , 9999でまでに登場する1の個数」と
「10000, 10001, ..., [1]ABCDで登場する1の個数」の２つに分けて考える．

前半の1の個数はまんま f(9999)（9が４つ）．
これはこのスレでも今までに何度も出てるけど，f(9がp個) = 10^{p-1} + 10× f(9がp-1個)．ただしf(9が0個)=0．

後半の1の個数をさらに「頭（５桁目）につく1の個数」と「下4桁に表れる1の個数」に分けて考える．
頭の1は後半のすべての数についている => 頭についた1の個数は ABCD + 1 個
下4桁に出現する1の個数の合計は，0, ..., ABCDまでに登場する1の個数と同じ => つまりf(ABCD)

全部足すと，f([1]ABCD) = f(９が４つ) + (ABCD + 1) + f(ABCD)．これが頭が1の場合の再帰的な計算式．

頭に2〜9のうちのどれかがつく場合は
f([Z]ABCD) = 10^4（←10000から19999の５桁目の1）
　＋ f(9が4つ)×Z（←頭が0,1,..,Z-1までの数の下４桁の1の合計） ＋ f(ABCD)（←頭がZの場合の下４桁の1の合計）

数式書いてる人はオフィスソフトの数式エディタで入力して
キャプしてトリミングして画像で貼って欲しい

可読性悪くて見る気おきない(´･ω･｀)

>>404のp=6で考えると

f(1M) = 600k + 1
f(2M) = f(1M) + (1M - 1) + f(1M - 1)
　= f(1M) + 1M - 1 + (f(1M) - 1)
　= 2 * f(1M) + 1M - 2
　= 2 * (600k + 1) + 1M - 2
　= 1200k + 2 + 1M -2
　= 1200k + 1M = 2.2M
f(3M) = f(2M) + f(1M - 1)
　= f(2M) + (f(1M) - 1)
　= 2.2M + ((600k + 1) - 1)
　= 2.2M + 600k = 2.8M
f(4M) = f(3M) + 600k = 3.4M
f(5M) = f(4M) + 600k = 4M
f(6M) = f(5M) + 600k = 4.6M
f(7M) = f(6M) + 600k = 5.2M
f(8M) = 5.8M
f(9M) = 6.4M
f(10M) = f(9M) + 600k + 1 = 7M + 1

f(1M) < 1M < f(2M)だから 1M〜2Mの間にf(n)=nがある可能性があり
f(3M) < 3M < f(4M)だから 3M〜4Mの間にf(n)=nがある可能性がある
f(5M) = 4Mだから 4M〜5Mの間は常にf(n)<nが成り立つ
2M < f(2M)=2.2M < f(3M)=2.8M < 3Mだから 2.2M〜2.8Mの間にf(n)=nがある可能性がある？

こんな感じで範囲絞って検索かけりゃ計算手間が減る？

グーグルも任天堂と同じ末路を歩むのか
学歴じゃイノベーションは起こせないというのに

訂正

f(1M)=600k < 1M < 2M < f(2M)=2.2Mだから 1M〜2Mの間にf(n)=nがある可能性があり
f(3M)=2.8M < 3M < f(4M)=3.4M < 4M だから 3M〜3.4Mの間にf(n)=nがある可能性がある
f(4M)=3.4 < f(5M)=4M < 4M + 1だから 4M〜5Mの間は常にf(n)<nが成り立つ
2M < f(2M)=2.2M < f(3M)=2.8M < 3Mだから 2.2M〜2.8Mの間にf(n)=nがある可能性がある？

問題としては中途半端なんだな
理詰めでかなり範囲を絞れるけど
馬鹿正直にコード書いても数分で出ちゃうっていう・・・

最大値がここからここまでの間にあるという証明をして、
プログラムで実際の値を求めるでいいのかな

試験ではこれを何分で解くの？
脳味噌どうなってるの

>>1のfはこんな感じか？


'Visual Basic 6.0
Public Function f(n&) As Long
　Dim r&, s$, l&, i&, k&, p&
　s = CStr(n)
　p = Len(s) - 1
　If p = 0 Then
　　r = IIf(CLng(Right$(s, 1)) > 0, 1, 0)
　ElseIf p > 0 Then
　　k = CLng(Left$(s, 1))
　　If k = 1 Then
　　　r = r + (p * (10 ^ (p - 1))) + 1
　　　r = r + CLng(Right$(s, p))
　　ElseIf k > 1 Then
　　　r = r + (k * p + 10) * (10 ^ (p - 1))
　　End If
　　r = r + f(CLng(Right$(s, p)))
　End If
　f = r
End Function

変だったから直した

'Visual Basic 6.0
Public Function f(n&) As Long
　Dim r&, s$, k&, p&
　s = CStr(n)
　p = Len(s) - 1
　If p > 0 Then
　　k = CLng(Left$(s, 1))
　　If k = 1 Then
　　　r = r + (p * (10 ^ (p - 1))) + 1
　　　r = r + CLng(Right$(s, p))
　　ElseIf k > 1 Then
　　　r = r + (k * p + 10) * (10 ^ (p - 1))
　　End If
　　r = r + f(CLng(Right$(s, p)))
　Else
　　r = IIf(n > 0, 1, 0)
　End If
　f = r
End Function

f(1)=1以降、f(n)<nになってるから、１以降ではじめにf(n)=nになるnは
１の数が２個以上あるはず

>>412
>f(1P)とf(2P)の間は必ずどの数を記述するのに1を使うから、この間、nがf(n)を追い越すことはない
>この後もn+1<f(nP)となるからn<f(n)

よくよく考えなおしてみたら、これ違うんじゃね？
f(2P)>2Pなんだから1.5P〜2Pの間でf(n)=nを満たす可能性があることは否定できないんじゃねえの？

やはり10^100まではしっかり調べないとダメじゃね

あーでもf(1.5P)=2.3P>1.5Pだからn=1.5Pに達する前に超えちゃうのか

これ、１以外の数は数えてもf(n)=nとなる数はないっぽい。
例えば２の数とか、３の数とか

N=A･10^n+B (1≦A≦9　0≦B＜10^n)とおくと
A=1のとき　f(N)=A･n･10^(n-1) + f(B) + (B+1)
A≠1のとき　f(N)=A･n･10^(n-1) + f(B) + 10^n

n≧10と仮定すると
A=1のとき
f(N)=A･n･10^(n-1) + f(B) + (B+1)≧A･10･10^(n-1) + (B+1)=A･10^n + (B+1)＞N
A≠1のとき
f(N)=A･n･10^(n-1) + f(B) + 10^n≧A･10･10^(n-1) + 10^n=A･10^n + 10^n＞A･10^n + B=N

∴n≦9

答え：ｇｇｒｋｓ

>>435
試してみたが、例えば2の場合、以下がヒットする
28,263,827
35,000,000
242,463,827
500,000,000
528,263,827
535,000,000

俺も3でやってみたらこうなった。
おもしれえなー

f3(0) = 0
f3(371,599,983) = 371,599,983
f3(371,599,984) = 371,599,984
f3(371,599,985) = 371,599,985
f3(371,599,986) = 371,599,986
f3(371,599,987) = 371,599,987
f3(371,599,988) = 371,599,988
f3(371,599,989) = 371,599,989
f3(371,599,990) = 371,599,990
f3(371,599,991) = 371,599,991
f3(371,599,992) = 371,599,992
f3(500,000,000) = 500,000,000

>>438
>>439
なるほど、桁の大きいところには存在するのか

>>434
よくわかんないけど、とりあえずn=1.5P〜2Pでf(n)=nになることはないよ
この間の数は全部1を含むから、n=1Pでn<f(n)となってる以上、nとf(n)の値が縮まることはない
（nは1増えるごとにf(n)は1以上増える）

あと気づいてるかもだけど、n+1<f(nP)は色々とカオスな書き損じ

4の場合

f4(0) = 0
f4(499,999,984) = 499,999,984
f4(499,999,985) = 499,999,985
f4(499,999,986) = 499,999,986
f4(499,999,987) = 499,999,987
f4(499,999,988) = 499,999,988
f4(499,999,989) = 499,999,989
f4(499,999,990) = 499,999,990
f4(499,999,991) = 499,999,991
f4(499,999,992) = 499,999,992
f4(499,999,993) = 499,999,993
f4(500,000,000) = 500,000,000

5と6は12億まで試したけど無いな

わからん。屁理屈こねろって指示されてるようにしか思えない。
虚数的な

7,8,9,0も12億までは無かった
もっとでかい場所で出てくんのかな

ああ桁が増えるほどボーナスゲーム時の収入がでかくなるのか

f(n)を展開していく公式はあるけど、先頭が0か1か2以上かで値が変わるのが
問題。結局展開式が組み合わせ的に増えて、総当り的になってしまう。

はじめの数199981の条件がもっと絞れればいいんだけど

ただ言えることは
f(9)=1
f(99)=20
f(999)=300
…
は、どの数字でも成り立つということだ

これプログラム作る以外で答え出せるの？
無理だと思うんだけど

0だろ
f(1)=1が同じになって、
f(n)=2のnは10、すなわちf(10)=2
これ以降は()内の数値>返り値になるから
f(1)が最大であり、f(0)=0が二番目に大きい

ところがどっこい199981でまた追いついてしまうのだ

>>450
スレ読まずに書き込むんじゃなかった、恥ずかしいわ
成る程一気に 1 の数が増えるのか

面白そうだからプログラム組んでみたいけど、
いかんせん手元にiphoneしかない

投資すれば投資するほどボーナスゲーム時の収支がでかい関数を作る場合の参考になりそう

N=A*10^nとすると、
A=1のとき、
　　f(N)=n10^(n-1)+1
A≠1のとき、
　　f(N)=A*n*10^(n-1)+10^n
と表せる。
先頭が１のときの傾き（10^n〜2*10^nの間の傾き）をXnと書くと、
Xn={f(2*10^n)-f(10^n)}/(2*10^n-10^n)≒1+n/10
一方、
先頭が２〜９のときの傾き（2*10^n〜10^(n+1)-1の間の傾き）をYnと書くと、
Yn={f(10^(n+1)-1)-f(2*10^n)}/(10^(n+1)-1-2*10^n)≒n/10
になる。

>>454続き
f(N)=Nとなるとき先頭が１の場合、
f(10^n+X)≒f(10^n)+(1+n/10)X=10^n+X　ただし、（0≦X≦10^n）
解くと、
X≒(10-n)/n * 10^n

範囲から、0≦10-n≦n
結局、5≦n≦10
近似してるので等号は＜に変わる可能性あり。

>>455続き、
10^n+X=(10/n)*10^n
n=5のとき、
N=(10/5)*10^5となるので、N=200000付近
n=6のとき、
X=(10/6)*10^6となるので、N=1666666付近
n=7のとき、
X=(10/7)*10^7となるので、N=14285714付近
x=8のとき、
X=(10/8)*10^8となるので、N=125000000付近
x=9のとき、
X=(10/9)*10^9となるので、N=1111111111付近
x=10のとき、
X=(10/10)*10^10となるので、N=10^10付近

>>455続き、 （訂正）
10^n+X=(10/n)*10^n
n=5のとき、
N=(10/5)*10^5となるので、N=200000付近
n=6のとき、
X=(10/6)*10^6となるので、N=1666666付近
n=7のとき、
N=(10/7)*10^7となるので、N=14285714付近
x=8のとき、
N=(10/8)*10^8となるので、N=125000000付近
x=9のとき、
N=(10/9)*10^9となるので、N=1111111111付近
x=10のとき、
N=(10/10)*10^10となるので、N=10^10付近

>>40
これじゃないのか？？

例えば１０００００から１００００００までの間に、６００００１個しか数字はない
仮にそれらがすべて１だったとしても、nが９０００００増えるのに対して
６００００１しかf(n)は増加しない。

実際はもっと増加は小さい
よって、抜かされることはない。

これであかん？

すまん、違ってたorz
5400000じゃんか。無視してくれ

各桁のg(n)=f(n)-nの最大値は
11. -7.
191. -59.
1991. -399.
19991. -1999.
199991. 1.
1999991. 200001.
って感じで、19…91になるっぽい。

N=A･10^n+B (1≦A≦9　0≦B＜10^n　nは正整数)
f(N)=Nを満たすとすれば
A=1のとき5≦n≦9
A=2のとき4≦n≦9
A=3のとき6≦n≦9
A=4のとき7≦n≦9
A=5のとき7≦n≦9
A=6のとき8≦n≦9
A=7のとき8≦n≦9
A=8のとき8≦n≦9
A=9のときn=9
ここまでは不等式ででた

>>1
ああ、５回ぐらい読んでやっと問題の意味がわかった
答えはいつぞや

こんなん分かる奴いるんか？
法則性があればだが

>>78
そうそう、その域だはこの一般化で法則がわかるかも
めんどい

>>421
ふーむふむ。サンクス
ちょっとづつ分かってきました

f(N)-N=0を満たす２以上の最小の数を N=A･10^n+B (1≦A≦9　0≦B＜10^n)とおく。
このとき、f(N)は次の性質を満たす。
A=1のとき　f(N)=A･n･10^(n-1) + f(B) + (B+1)
A≠1のとき　f(N)=A･n･10^(n-1) + f(B) + 10^n

A=1のとき、
f(N)-N=n･10^(n-1) + f(B) + (B+1) - 10^n - B = (n-10)10^(n-1) + f(B) + 1
最大値はB=10^n-1のときで、 max(f(N)-N)=(2n-10)10^(n-1) + 1　… (1)

A≧2のとき、
f(N)-N=A･n･10^(n-1) + f(B) + 10^n - A･10^n - B = {A(n-10) + 10}10^(n-1) + f(B) - B
この関数が最小となるのは、(n-10)≦0であるから、A=2かつ、
f(B)-B≦0であるから、B=0または1である。
すなわち、max(f(N)-N) = {(2n-10) - 10}10^(n-1)　… (2)

(1)≧(2)であるから、A=1,B=10^n-1のとき、f(N)-Nは最大となり、max(f(N)-N)=(2n-10)10^(n-1) + 1 である。
max(f(N)-N)≧0となるのは、n=5、N=10^5+10^4-1=199999のときであり、
f(199999)-199999=1
である。そこで、ここから遡っていくと、
f(199991)-199991=1
f(199990)-199990=0
f(199981)-199981=0　★
f(199980)-199980=-1
以降、最上位桁は１であるため、f(N)-Nは少なくとも同じか1以上下がる。
ゆえに、f(N)=Nを満たす２以上の最小の数は19981である。

>>467　最後の値ミスった（笑）これでいいはず。

f(N)-N=0を満たす２以上の最小の数を N=A･10^n+B (1≦A≦9　0≦B＜10^n)とおく。
このとき、f(N)は次の性質を満たす。
A=1のとき　f(N)=A･n･10^(n-1) + f(B) + (B+1)
A≠1のとき　f(N)=A･n･10^(n-1) + f(B) + 10^n

A=1のとき、
f(N)-N=n･10^(n-1) + f(B) + (B+1) - 10^n - B = (n-10)10^(n-1) + f(B) + 1
最大値はB=10^n-1のときで、 max(f(N)-N)=(2n-10)10^(n-1) + 1　… (1)

A≧2のとき、
f(N)-N=A･n･10^(n-1) + f(B) + 10^n - A･10^n - B = {A(n-10) + 10}10^(n-1) + f(B) - B
この関数が最小となるのは、(n-10)≦0であるから、A=2かつ、
f(B)-B≦0であるから、B=0または1である。
すなわち、max(f(N)-N) = {(2n-10) - 10}10^(n-1)　… (2)

(1)≧(2)であるから、A=1,B=10^n-1のとき、f(N)-Nは最大となり、max(f(N)-N)=(2n-10)10^(n-1) + 1 である。
max(f(N)-N)≧0となるのは、n=5、N=10^5+10^4-1=199999のときであり、
f(199999)-199999=1
である。そこで、ここから遡っていくと、
f(199991)-199991=1
f(199990)-199990=0
f(199981)-199981=0　★
f(199980)-199980=-1
以降、最上位桁は１であるため、f(N)-Nは少なくとも同じか1以上下がる。
ゆえに、f(N)=Nを満たす２以上の最小の数は199981である。

すげーこんなん根気強く集中して解けるとかどんな能力だよ
日本の総理大臣になってくださいませ

'Visual Basic 6.0
Public Function f(ByVal n&) As Long
Dim r&, s$, k&, p&
s = CStr(n)
p = Len(s) - 1
If p > 0 Then
k = CLng(Left$(s, 1))
If k = 1 Then
r = r + (p * (10 ^ (p - 1))) + 1
r = r + CLng(Right$(s, p))
ElseIf k > 1 Then
r = r + (k * p + 10) * (10 ^ (p - 1))
End If
r = r + f(CLng(Right$(s, p)))
Else
r = IIf(n > 0, 1, 0)
End If
f = r
End Function

'>>470の続き

Public Function nextNum(ByVal x&, ByVal r&) As Long
Dim z&, i&, l&, s$, d1&, d10&
s = CStr(x)
d1 = CLng(Right$(s, 1))
If d1 = 0 Then
x = x + 1
Else
l = Len(s)
If l > 1 Then
d10 = CLng(Mid$(s, l - 1, 1))
If (d10 = 0) Or (d10 = 9) Then
z = x + 10 - d1
Else
z = x + 11 - d1
End If
Else
z = x + 10 - d1
End If
x = IIf(z > r, x + 1, z)
End If
nextNum = x
End Function

＞f(B)-B≦0であるから

ここは何故っすか？

もしかして、はじめの
＞f(N)-N=0を満たす２以上の最小の数を

はf(N)-N≧0？

'470,471の続き、ほぼ一瞬で>>364の数字が出る、あとはオーバーフローの壁に阻まれる
Public Sub search1()
Dim x&, y&, z&, r&, q&
Do
r = f(x)
If x > r Then
y = x
Do
y = y \ 2&
z = x + y
q = f(z)
Loop While x < q
If x <> z Then
x = z
r = q
Else
x = nextNum(x, r)
End If
ElseIf x < r Then
x = r
r = f(x)
Else
Debug.Print x
x = nextNum(x, r)
End If
Loop While x < &H7FFFFFFF
End Sub

Google「うはｗこんな問題出す俺かっこいい…」

>>470 >>471 >>473 をコピペで
エクセルのVBAマクロで実行してできる

エクセル2010で確認済み

VBAの標準モジュールに>>470,471,473をコピペ
VBAのメニューの表示からイミディエイト ウインドウを表示

イミディエイト ウィンドウ内に
search1
と入力しエンターを入れれば実行される
イミディエイト ウィンドウ内に>>364の数字がずらっと表示されて
最後はオーバーフローエラーで止まる

32bit整数では収まりませんな

オーバーフローエラーを発生させないためには>>470の代わりに以下の修正されたコードを使えばおｋ

'Visual Basic 6.0
Public Function f(ByVal n&) As Long
On Error GoTo hoge
Dim r&, s$, k&, p&
s = CStr(n)
p = Len(s) - 1
If p > 0 Then
k = CLng(Left$(s, 1))
If k = 1 Then
r = r + (p * (10 ^ (p - 1))) + 1
r = r + CLng(Right$(s, p))
ElseIf k > 1 Then
r = r + (k * p + 10) * (10 ^ (p - 1))
End If
r = r + f(CLng(Right$(s, p)))
Else
r = IIf(n > 0, 1, 0)
End If
f = r
Exit Function
hoge:
f = &H7FFFFFFF
End Function

>>470の代わりに>>478のコードを使うと>>364の数値の後に1111111110が表示されて終わる

俺の書いたコードだとnは2G(2,000,000,000)までしか検索できない

>>472
言い方が間違ってた。

f(N)-N=0を満たす２以上の最小の数と[同じ桁の数]を N=A･10^n+B (1≦A≦9　0≦B＜10^n)とおく。 かな

一般にはf(B)-B≦0ではないけど、0,1を除いて最初にf(N)=Nとなる桁で、
はじめて、max(f(N)-N)≧0になるはず。
Bの桁数はNの桁数より小さいから、Bの桁ではmax(f(B)-B)≦0でないと
その桁に条件を満たす数があることになってしまう。

お前らまだやってたのか。
先に証明や答えがどっかに書いてないかググれよ。
それにいくらコード書いたところで停止条件を定義できなきゃ意味ないし。
1111111110で止まるんなら1111111110に目星付けて最大値であることが証明できないか考えろ。

>>1じゃないが問題のソースはここだろ。next largestが複数の意味に解されることも仮定済み。

Computer Musing - Google Labs Aptitude Test, question 17
http://pdejoue.perso.neuf.fr/section_stuff/technical/google_labs_aptitude_test_17.php

グーグルの問題用紙はここ。解けない問題があると取っ掛かりきりになるのはアスペだぞ。

http://googleblog.blogspot.jp/2004/09/pencils-down-people.html

この認識で合ってる？このf(n)を作ればいいんだな？
n = 1,599,981 のとき

f(n)=
　f(999,999)　　 <= ( 0 - 999,999 までの "1" 出現回数 )
＋(599,981 + 1)　<= ( 頭の一桁 "1" が 599,981 回 + 1 回 出現 )
＋f(599,981)　　 <= ( 1,000,000 - 1,599,981 までの "1" 出現回数 )
------------------------ ここから１回目の再帰処理 ------------------------
�@ f(999,999) の値を求める
f(999,999)=
　10^6　　　　　<= ( 100,000 - 199,999 までの 頭一桁分の "1" 出現回数 )
＋f(99,999)*9　 <=　(( 0 - 99,999 での出現回数 )
　　　　　　　　　＋( 100,000 - 199,999 での出現回数 )
　　　　　　　　　＋( 200,000 - 299,999 での出現回数 )
　　　　　　　　　＋．．．
　　　　　　　　　＋( 800,000 - 899,999 での出現回数 ))
＋f(99,999)　　 <= ( 900,000 - 999,999 までの "1" 出現回数 )

�A f(599,981) の値を求める
f(599,981)=
　10^6　　　　　<=　( 100,000 - 199,999 までの 頭一桁分 "1" 出現回数 )
＋f(99,999)*5　 <=　(( 0 - 99,999 での出現回数 )
　　　　　　　　　＋( 100,000 - 199,999 での出現回数 )
　　　　　　　　　＋( 200,000 - 299,999 での出現回数 )
　　　　　　　　　＋．．．
　　　　　　　　　＋( 400,000 - 499,999 での出現回数 ))
＋f(99,981)　　 <= ( 500,000 - 599,981 までの "1" 出現回数 )
------------------------ ここから２回目の再帰処理 ------------------------
�Bf(99,999) の値を求める
�Cf(99,981) の値を求める