さくBは折り紙を折っている

saku B is folding origami.

753数の数え上げ

引き続きAtCoderで遊んでます。さっくです。
今日はAtCoderに出てきた「753数」を紹介します。
ある自然数Nが「753数」であるとは

  • Nの各桁が7,5,3のいずれかである・・・(1)
  • 7,5,3がそれぞれ少なくとも1回以上Nに含まれる・・・(2)

この2つの条件を満たすことを言います。

 

例えば753や37575、55555537などが753数です。

一方、7775や35、555は753数ではありません。

 

 AtCoderでは

「与えられた自然数Nに対して、N以下の753数の個数を求めよ」

という問題でした。

 

今回は少し問題を変えて、

N桁の753数の個数を求めよ」

という問題について考えてみたいと思います。

 

まず、上の条件(1)を満たし、条件(2)を満たさない数を「準753数」と呼ぶことにしましょう。

 N桁の準753数は3^N個ですね。

なぜなら、各桁には7,5,3の3通りの数字の選び方があるからです。

 

twitter上で見かけたある方のつぶやきでベン図の有用性を改めて認識したので、

ベン図を描いてみます。

 

f:id:sakusaku858:20190117004032p:plain

 

求めたいのはグレーの部分(A)です。

H=0です。3も5も7も含まない準753数は0個。

E=F=G=1です。3しか含まないN桁の753数は1個です。

B=C=D=2^N-2です。例えば7含まないN桁の753数は2^N個です。

したがって

A=3^N-3(2^N-2)-3=3^N-3\cdot 2^N+3

です。

ゆえにN桁の753数は3^N-3\cdot 2^N+3個でした。

 

これをうまく使って、与えられた自然数Nに対して、N以下の753数の個数を高速に求められないかなぁ。などと考えていました。