答えが知りたい

 投稿者：GAI  投稿日：2009年 8月18日(火)18時04分28秒
  ＜問題＞
整数ｎが与えられたとき、０～ｎの間の全ての数を書くのに必要とされる「１」の数を返す関数をｆ(n)とする。（例　f(13)=6 )
f(1)=1であるが、一般にf(n)=n
となるような、２番目に大きいｎを求めよ。
なる問題の答えを知るプログラムをお教えください。 		 

Re: 答えが知りたい

 投稿者：山中和義  投稿日：2009年 8月18日(火)20時22分41秒
  > No.485[元記事へ]

GAIさんへのお返事です。

> f(1)=1であるが、一般にf(n)=nとなるような、２番目に大きいｎを求めよ。

!n=13の場合
!0,1,2,3,4,5,6,7,8,9,10,11,12,13より、「１」の数は６個となる。
!∴f(13)=6

OPTION ARITHMETIC NATIVE

LET fn=0 !１の数

FOR n=0 TO 2^31-1 !範囲

   LET t=n !０～ｎを表現する

   DO WHILE t>0 !各桁が１の数をかぞえる
      IF MOD(t,10)=1 THEN LET fn=fn+1
      LET t=INT(t/10)
   LOOP

   IF fn=n THEN PRINT "f(";n;")=";fn !f(n)=nのなら

NEXT n

END


実行結果 
f( 0 )= 0
f( 1 )= 1
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( 199990 )= 199990
f( 200000 )= 200000
f( 200001 )= 200001
f( 1599981 )= 1599981
f( 1599982 )= 1599982
f( 1599983 )= 1599983
f( 1599984 )= 1599984
　：
　：
 

Re: 答えが知りたい

 投稿者：山中和義  投稿日：2009年 8月20日(木)10時17分38秒
  > No.486[元記事へ]

●各桁での調査範囲はあるか？

前出のプログラムでは、すべての数を検証しているが、次のプログラムを実行することで、
その結果の推測より、範囲が限定できそうだ。
OPTION ARITHMETIC NATIVE

LET fn=0 !１の数

FOR k=1 TO 12 !範囲

   LET n=10^k-1 !9,99,999,9999,…
   PRINT "f(";n;")=";

   FOR i=INT(n/10)+1 TO n !０～ｎを表現する

      LET t=i !各桁の１の数をかぞえる
      DO WHILE t>0
         IF MOD(t,10)=1 THEN LET fn=fn+1
         LET t=INT(t/10)
      LOOP

   NEXT i

   PRINT fn !結果を表示する

NEXT k

END

実行結果 
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( 999 )= 300 より、n=100～300の範囲を調べればよいことになる。
（証明）
１桁の場合、自明。
２桁の場合、一の位が１は、10通り。十の位が１は、10通り。2*10=20通り。
ｋ桁の場合、１つの桁を１に固定したとき、残りの桁の場合の数は、10^(k-1)通り。
これがk桁あるので、k*10^(k-1)通りとなる。
（証明終り）
したがって、０～10^k-1（kは桁数）では、「１」の数は f(10^k-1)=k*10^(k-1) となる。

また、f(10^10-1)=10^10から、f(10,000,000,000)=10,000,000,001となる。
これより、n=10^10以降はf(n)>nが予想される。


　０～10^10の範囲で見つかる1,111,111,110は、「最大の数？」
なら

　　> f(1)=1であるが、一般にf(n)=nとなるような、２番目に大きいｎを求めよ。
は、
　535,200,001 		 

Re: 答えが知りたい

 投稿者：荒田浩二  投稿日：2009年 8月21日(金)12時03分41秒
  > No.489[元記事へ]

p進法についても10進法と同様のことが言えそうです。
『各数値をp進法で表現したとき,f(n)=nとなる最大のnは n=p^(p-1)+p^(p-2)+…+p^2+p』
つまり「末位が0で他の桁が1であるp桁の数」ということです。p=4ならばn=1110
山中和義さんの投稿記事にある"10"を"p"に置き換えれば,ほとんどの場合p進法に一般化できそうです。

OPTION ARITHMETIC NATIVE
DECLARE FUNCTION change
DIM sum1(2 TO 10),max_n(2 TO 10)
MAT sum1=ZER
PRINT USING "##### ############(=>#########)":"p進法","f(n)=n最大値","10進数"
FOR n=1 TO 7^7
   FOR p=2 TO 7  ! p=8以上は個々に計算しないと時間がかかる
      LET x=n
      DO
         IF MOD(x,p)=1 THEN LET sum1(p)=sum1(p)+1
         LET x=INT(x/p)
      LOOP UNTIL x=0
      IF sum1(p)=n THEN LET max_n(p)=n ! f(n)=n
   NEXT p
NEXT n
FOR p=2 TO 10
   PRINT USING "  ## ###########  (=##########)":p,change(max_n(p),p),max_n(p)
NEXT p
!
FUNCTION change(x,p) ! 10進数をp進数に変換
   LET s,k=0
   DO
      LET s=MOD(x,p)*10^k+s
      LET k=k+1
      LET x=INT(x/p)
   LOOP UNTIL x=0
   LET change=s
END FUNCTION
END 		 

Re: 答えが知りたい

 投稿者：山中和義  投稿日：2009年 8月24日(月)16時03分16秒
  > No.491[元記事へ]

「場合の数」を算出することで、f(n)の値を再帰処理で求めます。
直接求めるので、個々の（大きな）値を得る場合はこちらの方が早いです。
前出のように０から順に求める場合は、０～ｎを毎回計算することになるので遅くなります。
!例　f(123)の場合
!100と23に分解する
!　3桁の数（最上位桁=1）
!　　1xx形式の数 = k桁目に(23+1)=24、(k-1)～1桁目にf(_99)=20
!　端数23
!　　f(23)
!　⇒
!　　20と3に分解する
!　　　2桁の数（最上位桁=2）
!　　　　1x形式の数 = k桁目に10^(2-1)=10、(k-1)～1桁目にf(_9)=1
!　　　　2x形式の数 = k～1桁目にf(_9)=1
!　　　端数3
!　　　　f(3)
!　　　⇒
!　　　　3と0に分解する
!　　　　　1桁の数（最上位桁=3）
!　　　　　　1形式の数 = 1桁目に10^(1-1)=1、(1-1)桁目にf(_)=0
!　　　　　　2形式の数 = 1桁目にf(_)=0
!　　　　　　3形式の数 = 1桁目にf(_)=0
!　　　　　端数0
!　　　　　　f(0)=0
!∴(24+20) + (10+1 +1) + (1+0 +0 +0) +0 = 57

FUNCTION f(n$,p) !０～ｎまでを列記したときの「１」の数　※n$は非負のp進法の数値
   local k,m,t$
   IF ExBVAL(n$,p)=0 THEN
      LET f=0
   ELSE
      LET k=LEN(n$) !桁数
      LET m=VAL1(n$(1:1)) !最上位桁に着目する
      LET t$=n$(2:LEN(n$)) !端数
      !PRINT n;k;m;t$ !debug

      IF m=1 THEN !(1xxx…x)の場合
         LET w=ExBVAL(t$,p)+1
      ELSE !(2xxx…x)、…、(9xxx…x)の場合
         LET w=p^(k-1)
      END IF
      LET f=( w + f(REPEAT$(STR1$(p:p),k-1),p)*m ) + f(t$,p) !k桁 + f(端数)
   END IF
END FUNCTION

LET STR1$="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" !p進法の数字
DEF VAL1(x$)=POS(STR1$,x$)-1

FUNCTION ExBVAL(n$,p) !n$を非負のp進法の数値とした値
   LET s=0
   FOR i=1 TO LEN(n$)
      LET s=s*p+VAL1(n$(i:i))
   NEXT i
   LET ExBVAL=s
END FUNCTION

FUNCTION ExBSTR$(n,p) !非負の整数nをp進法で表記する
   LET s$=""
   DO
      LET nn=INT(n/p)
      LET t=n-nn*p !MOD(n,p)
      LET s$=STR1$(t+1:t+1)&s$ !下の位から
      LET n=nn
   LOOP UNTIL n=0
   LET ExBSTR$=s$
END FUNCTION

!------------------------------ ここまでがサブルーチン


PRINT f("1111111110",10) !10進法

PRINT ExBVAL("111110",6); f("111110",6) !６進法


LET p=4 !４進法
FOR n=0 TO p^p
   LET w$=ExBSTR$(n,p)
   IF f(w$,p)=n THEN PRINT "f(";n;")=";n, STR$(p);"#";w$
NEXT n

END
 

戻る