割り切れない数

『3桁の整数の中で2でも3でも13でも割り切れない整数は何個あるか』という問題なのですが楽な解法ってありますか？

No.6 回答者： yuitor 回答日時： 2011/01/14 10:38

３桁の整数は900あるのでその中から

A:2で割り切れるもの
B:3で割り切れるもの
C:13で…
D:6(2×3)で…
E:26(2×13)で…
F:39（3×13）で…
G:78（2×3×13）で…

の数をそれぞれ計算し

A+B+C-D-E+F

を求め、900とその数の差を求めるのが一番メジャーで楽ではないかと。

No.5 回答者： kumipapa 回答日時： 2007/08/08 09:32

#4さん、失礼ですが勘違いをされています。

１３進数で表したときの下一桁は、元の整数Ｎを
Ｎ＝１３ｎ＋ｍ　（ｎは整数、ｍ＝０，１，・・・１２）
と表したときのｍと同じです。
当然ですが、ｍの値（つまり１３進数の１番下の桁）だけで、Ｎが２や３で割り切れるかどうかを判断することはできません。
例えば、１１(13)＝１４(10)、２１(13)＝２７(10)ですから、１３進数の１桁目が１でも、２や３で割り切れたり、割り切れなかったりします。
ちなみに、１００から９９９で２，３，１３で割り切れない数字の個数は２７８個です。

p進数にして、上の桁を考慮しなくて良いようにするためには、78進数にしなければなりません。下一桁の数字（あえて10進数で書くと0～77）の中から２，３，１３で割り切れない数を探す、ということになりますが、結局、１００～９９９から個数を求めるのと計算量が減るかというと疑問です。

No.4 回答者： maku_x 回答日時： 2007/08/08 00:22

質問者様の学年が分かりませんので、学年によっては難解な理論を使うことになってしまいますが、一気とはいかないまでも、比較的簡単に答えが出る方法はあります。

これは以前、フジテレビ系列で放送された「たけしのコマネチ大学数学科」と言う番組の中で紹介された解法をほぼそのまま使ったものです。知識レベルとしては、高校で習う「情報」と言う科目を履修したことを想定しています。

基本的に人間が使う数は、1桁当たり0～9までの数を組み合わせて使います。これを10進数と言います。仮に1桁当たり 0～12までの数を使った数、言わば 13進数を考えてみます。一応 0～12を一桁で表すため、0,1,2,3,4,5,6,7,8,9,a,b,c の12種類の記号(数)を使うことにします。2でも3でも13でも割り切れない整数は、13進数で考えると、この13種類のうち 1,4,5,7,b の5種類であることが分かります。13進数で考えれば、下1桁以外の数は、どんな数でも良く、2でも3でも13でも割り切れないかどうかは、下1桁の値だけで決まります。一方10進数の3桁の整数は、100～999 までです。これを13進数で表現すると、
79～5bb
となります。下1桁が半端な範囲の数は、後で数えるとして、このうち下1桁の切りが良い 80～5b0 に含まれる、2でも3でも13でも割り切れない整数は、下1桁が、1,4,5,7,b の5種類の場合です。この個数を求める際に 13進数として計算すると、
((5b0 - 80)÷10) × 5 = 53×5 + 1 = 202
※蛇足ですが、10進数ではありませんから、÷10) × 5 をまとめて、÷2 とするのは間違いですから、ご注意を。
これを10進数で表現すると、340 となります。
次に、79～7b までに含まれる、2でも3でも13でも割り切れない整数は、一番下の1桁が、b の 1つです。
次に、5b1～5bb までに含まれる、2でも3でも13でも割り切れない整数は、一番下の1桁が、1,4,5,7,b の 5つです。
これらを全部足せば、340 + 1 + 5 = 346
すなわち、3桁の整数の中で2でも3でも13でも割り切れない整数は 346個と言う答えを得ます。

※ 10進数以外の数を人間が扱うと、すぐに 10進数と間違えて混乱しますし、10進数と13進数の間の変換は、手計算で行うのはかえって手間が掛かってしまいますね。電卓を使わないと面倒ですね。柔軟な思考能力を持つ人向きの解法です。

※ なお、この理屈を使うと、ある値aから、十分な大きな値bの間に存在する、2でも3でも13でも割り切れない整数である確率は 5/13 ですから、(b + 1 - a)*5/13、a=100, b=999 で (999 + 1 - 100)*5/13 = 346.15... と、大体近い値が出ますが、これはあくまで目安に過ぎません。

No.3 回答者： kumipapa 回答日時： 2007/08/07 21:58

楽な解法ですか・・・

普通の方法が、「２、３、１３のいずれかで割り切れる数の個数」を求めて、全体から引くのだとすると、確かに計算ばかりで大変ですね。

こういうのはだめですか？

２でも３でも割り切れない数は、整数 n を用いて、6n+1 または 6n+5で表せるので、１００から９９９にある、6n+1と6n+5の個数を求める。
次に、２でも３でも割り切れないが、１３で割り切れる数は 78n+13 または 78n+65で表せるので、やはり個数を求めて、先の個数から引く。

大して変わりませんか。
78n+13, 78n+65っていうところは説明（証明）が必要になるでしょうし、かえって面倒でしょうか。

No.2 回答者： higotarou 回答日時： 2007/08/07 19:29

余事象を使いましょう。

全体から2でも3でも13でも割り切れない整数を引けば答えがでます。但し重複には気をつけよう。これが、一般的な解法です。

No.1 回答者： noname#43069 回答日時： 2007/08/07 16:58

それぞれの数で割り切れる数（倍数）の数を求めて、かつ「重複して割り切れてしまう数（公倍数）の調整」をすれば良いです。

この回答へのお礼

ありがとうございます。
他に一気に答えが出てしまう解法なんてありませんよね？

お礼日時：2007/08/07 17:03