SỐ HỌc giải một số BÀi toán của xec-pin-xki



tải về 105.27 Kb.
Chuyển đổi dữ liệu17.08.2016
Kích105.27 Kb.
#20835
SỐ HỌC

1. GIẢI MỘT SỐ BÀI TOÁN CỦA XEC-PIN-XKI (WACLAW SIERPINSKI)

Bạn đọc yêu thích môn Số học, chắc đã có lần đọc cuốn “250 bài toán số học” (1) (bản dịch tiếng Nga 1968), tác giả là nhà toán học Ba Lan nổi tiếng. Cuốn sách được xuất bản vào những năm giữa thế kỉ trước, sức hấp dẫn của sách là tính suy luận cao, chặt chẽ. Ngày nay với máy tính, chúng ta có thể làm cho lời giải càng thú vị hơn.



Bài 1: Chứng minh rằng trong hệ thập phân, số 3!!! (3 lần giai thừa liên tiếp) có nhiều hơn 1000 chữ số và tính số chữ số “0” ở phần đuôi của số đó.

Giải bằng Maple: Giải trên máy tính với phần mềm Maple V, release 5, phiên bản dùng cho học sinh (Maple là phần mềm tính toán rất mạnh, phạm vi sử dụng rất rộng trong khoa học, kĩ thuật).

Để giải bài toán này có ba lệnh: Mỗi lệnh ứng với mỗi dòng, bắt đầu bằng “>lệnh tương ứng”, kết quả tính là các dòng tiếp theo.



Lệnh 1: Tính giá trị của N =((3!)!)!, với lệnh tương ứng >N:= ((3!)!)!;

Lệnh 2: Tính số chữ số có trong N, với lệnh tương ứng >length(%);

Lệnh 3: Chia N cho số 10k, với lệnh tương ứng >N/10^k;

Lệnh 1 cho ngay giá trị của N. Vì không muốn đếm trực tiếp số chữ số “0”, ta sử dụng lệnh 3, k cần chọn cho thích hợp, chẳng hạn như k = 180, kết quả không phải là số tận cùng bằng 0. Do đó phải lấy k nhỏ hơn, ví dụ k =170, kết quả là một số tận cùng bằng 8 số “0”. Từ kết quả tính suy ra số N có 178 số “0” ở phần đuôi.

Xem chương trình Sohoc1 sau đây:

>N:=(((3!)!)!); (lệnh 1)

N:=26012189435657951…5683339509760000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

>length(%); (lệnh 2)

1747

>N/10^170; (lệnh 3)



N:=26012189435657951…56833395097600000000

Lời giải: Ta có: 3! = 6, 3!! = 6! = 720 và 3!!! = 720! > (99!).100621> 101242. Vậy số 3!!! có hơn 1000 chữ số.

Để giải tiếp phần sau, ta cần áp dụng một định lí: Nếu m là số tự nhiên và p là ước nguyên tố của m! thì số mũ lớn nhất của p trong khai triển của m! được tính bằng công thức: + + +..., với [x] (phần nguyên của x) là số nguyên lớn nhất nhỏ hơn hoặc bằng x.

5 là ước nguyên tố của 3!!! = 720!, vậy số mũ lớn nhất của 5 trong khai triển của 720! là: + + + = 144 + 28 + 5 + 1 = 178.

2 cũng là ước nguyên tố của 3!!! = 720!, số mũ lớn nhất của 2 trong khai triển của 720! cũng tính tương tự và số mũ ấy lớn hơn = 360.

Vậy số 3!!! tận cùng bằng 178 chữ số “0”.

Bài 2: Số 211213  1 viết trong hệ thập phân có bao nhiêu chữ số? (Theo tác giả cuốn sách (1), đây là số nguyên tố lớn nhất được biết vào thời cuốn sách được xuất bản bằng tiếng Ba Lan).

Giải bằng Maple: Thực ra muốn tính số chữ số của M = 211213 1 chỉ cần một lệnh, máy còn có thể cho ta giá trị của M, nhưng với hàng nghìn chữ số rất khó đếm trực tiếp được. Sau đây là 9 lệnh, chia thành ba nhóm giúp ta hiểu biết cặn kẽ hơn:

Lệnh 1: Tính số chữ số (chiều dài) của M = 211213;

Lệnh 2: Tính số chữ số của 2112;

Lệnh 3: Tính số chữ số của 21121;

Lệnh 4: Tính giá trị của 2112;

Lệnh 5: Tính giá trị của 21121;

Lệnh 6: Tính giá trị của 211213 – 1;

Lệnh 7: Số 2112  1 là số nguyên tố, đúng hay sai? Máy trả lời: sai;

Lệnh 8: Phân tích số 2112  1 ra thừa số nguyên tố: tích là 11 thừa số nguyên tố khác nhau với số mũ đều là 1;

Lệnh 9: Số 21121  1 là số nguyên tố, đúng hay sai? Máy trả lời: sai. Rất tiếc là khả năng của Maple V dùng cho học sinh không cho phép ta đi xa hơn nữa.

Xem chương trình Sohoc2 sau đây:



(lệnh 1)

3376

(lệnh 2)

34

(lệnh 3)

338

^112; (lệnh 4)

5192296858534827628530496329220096

>2^1121; (lệnh 5)

28485584767929776325836961026864930432818743280806019459942075224090226830957438015279762418082902111260148001310186947949444413350446219858868800518201024125360172694307110297079097105663248523889134084871889987070168265176393882645782144813006754426704646074154769941989706178901555015758166885268840583722361472048254005268531906609152

>2^112131; (lệnh 6)

28141120136973731…87696392191

>isprime(2^1121); (lệnh 7)

false

>ifactor(2^1121); (lệnh 8)



(3) (5) (17) (29) (43) (113) (127) (257) (54410972897) (15790321) (5153)

>isprime(2^11211); (lệnh 9)



false

Lời giải: Rõ ràng là hai số 211213  1 và 211213 có cùng số chữ số vì chúng chỉ khác nhau ở chữ số cuối cùng. Ta chỉ cần tính số chữ số của số 211213.

Nếu n là số tự nhiên viết dưới dạng 10x, với x là số thực lớn hơn hoặc bằng 0, ta có: 10[x] ≤ n < 10[x]+ 1, từ đó suy ra số n có [x] + 1 chữ số.

Ta có: 211213 = . Vì log102 = 0,30103… nên 3375 < 11213 log22 < 3376, vậy số 211213 1 có 3376 chữ số (trong hệ thập phân).

Bài 3: Trong hệ thập phân, số 211212(211213  1) có bao nhiêu chữ số.

Theo tác giả cuốn sách (1), đây là số hoàn hảo lớn nhất được biết vào thời điểm này. Số hoàn hảo là số có tổng các ước bằng chính số đó, ví dụ 6 = 1 + 2 + 3 (không kể 6).



Giải bằng Maple: Thực ra chỉ cần một lệnh là có ngay đáp số. Để có thể hiểu thêm chi tiết, ta dùng bốn lệnh:

Lệnh 1: Tính số chữ số của số 211212;

Lệnh 2: Tính số chữ số của số 211213 – 1;

Lệnh 3: Tính số chữ số của số 211212 (211213 – 1);

Lệnh 4: Tính số 211212 (211213 – 1).

Xem chương trình Sohoc3 sau đây:

>length(2^11212); (lệnh 1)

3376

>length(2^112131); (lệnh 2)



3376

>length(2^11212*(2^112131)); (lệnh 3)



6751

>2^11212*(2^112131); (lệnh 4)

395961321281794…02691086336

Ta có nhận xét là tổng số chữ số của hai thừa số hơn số chữ số của tích đúng một đơn vị. Mặc dù Maple cho ta giá trị của tích hai số nhưng thật khó khi đếm số chữ số của gần ba trang giấy. Vì số quá lớn nên Maple V cũng không thể cho biết các ước số để kiểm tra tính “hoàn hảo” của nó !!



Lời giải: Ta có: N = 211212 (211213  1) = 222425  211212.

Trước hết, ta tìm xem số 222425 có bao nhiêu chữ số.

Vì 22425.log10 2 = 22425. 0,30103 = 6750,597.. (xem bài 2) nên số 222425 có 6751 chữ số. Ta lại có 222425 > 106750100,597. Vì 100,597 > 101/2 > 3 nên 106751 > 222425 > 3.106750, từ đó suy ra chữ số thứ nhất của số 222425 phải lớn hơn hoặc bằng 3. Cho nên số chữ số của số 222425 sẽ không thay đổi khi ta trừ đi một số có số chữ số ít hơn, vậy số N có 6751 chữ số.

Bài 4: Chứng minh rằng trong dãy số vô hạn: 1, 31, 331, 3331,... có vô số hợp số, tìm hợp số nhỏ nhất.

Giải bằng Maple: Chương trình gồm 22 lệnh, chia thành hai nhóm:

Nhóm 1: Cho công thức của dãy số, lập 8 số hạng đầu tiên của dãy số, kiểm tra xem các số hạng đó có là số nguyên tố không gồm các lệnh từ 1 đến 10, lệnh 13, 14, 16, 19 và 22.

Nhóm 2: Tìm số hạng là hợp số: là hợp số nhỏ nhất trong dãy số, số đó có 9 chữ số. Khi là hợp số, yêu cầu máy phân tích ra thừa số nguyên tố gồm các lệnh 11, lệnh 12.

Tiếp tục tìm trong dãy số, số nào là số nguyên tố càng có nhiều chữ số càng tốt, ta chỉ cần ba lệnh:



Lệnh 20: Cho số A = 333333...31.

Lệnh 21: Chiều dài của A.

Lệnh 22: A có là số nguyên tố không?

Lần lượt thay đổi số chữ số trong A, chẳng hạn khi A có 60 chữ số, Maple lại cho biết A là số nguyên tố !!!

Xem chương trình Sohoc4 sau đây:

>f:=n>(10^n7)/3: (lệnh 1)

>map (f,[1,2,3,4,5,6,7,8]); (lệnh 2)

[1, 31, 331, 3331, 33331, 333331, 3333331, 33333331]

>isprime(331); (lệnh 3)



true

>isprime(3331); (lệnh 4)



true

>isprime(33331); (lệnh 5)



true

>isprime(333331); (lệnh 6)



true

>isprime(3333331); (lệnh 7)



>isprime(33333331); (lệnh 8)



true

>isprime(333333331); (lệnh 9)



false (đây là hợp số nhỏ nhất)

>isprime(3333333333333331); (lệnh 10)



false

>ifactor(3333333333333331); (lệnh 11)

(199) (16750418760469)

>ifactor(3333333333333333333333333333331); (lệnh 12)

(1985954448389527097) (2445767) (686269)

>isprime(33333333333333333331); (lệnh 13)



false

>isprime(3333333333333333333333333333333333333331); (lệnh 14)



true

>length(3333333333333333333333333333333333333333);



(lệnh 15)

40

>isprime(3333333333333333333333333333333333333331);



(lệnh 16)

true

>isprime(33333333333333333333333333333333333333333331); (lệnh 17)



false

>isprime(3333333333333333333333333333333333333333333333331); (lệnh 18)



false

>isprime(333333333333333333333333333333333333333333333333333333333331); (lệnh 19)



true

>A:=333333333333333333333333333333333333333333333333333333333331: (lệnh 20)

>length(A); (lệnh 21)

60

>isprime(A); (lệnh 22)



true

Lời giải: Số hạng tổng quát của dãy số là .

Ta có 102152 (mod 17), do đó 108161 (mod 17), tức là 109107 (mod 17).

Như vậy 10161 (mod 17), tức là 1016k+97 (mod 17), với k = 0, 1, 2, … nên 17 là ước của số (1016k+9  7). Ta kết luận số , với k = 0, 1, 2, … là hợp số.

Vậy giá trị nhỏ nhất ứng với k = 0 là số (109  7) = 333333331.

Trong dãy số đã cho, còn các số là hợp số có dạng khác không? Xuất phát từ đẳng thức 102 5 (mod 19), ta có 104 25 6 (mod 19) và 1012637 (mod 19) vì thế 1018k1 (mod 19), với k = 0, 1, 2,... tức là 19 là ước của số (1018k+12  7), với k = 0, 1, 2,… chẳng hạn như số (1012 7) là hợp số.

Lưu ý. Trong đề ra của bài toán, tác giả cuốn sách (1) nói rằng để giải được phần thứ hai vào thời điểm đó có thể dùng đến bảng số nguyên tố gọi là bảng “sáu triệu số nguyên tố đầu tiên”. Trong lời giải, tác giả đặt câu hỏi: Trong dãy số đã cho có vô số số nguyên tố hay không?”. Ví dụ như Maple đã cho ta số A với 60 chữ số là số nguyên tố nhưng câu trả lời tổng quát còn bỏ ngỏ!

Bài 5: Tìm tất cả các số tự nhiên lớn hơn 1 sao cho: (n  1)! + 1 = n2.

Giải bằng Maple: Chương trình gồm ba nhóm lệnh:

Nhóm 1: Tìm được n = 5, thoả mãn điều kiện của đầu bài, thử lại rằng với n > 5 thì (n 1)! +1 luôn luôn lớn hơn n2, bao gồm các lệnh 1, 2, 3.

Nhóm 2: Tìm giá trị của n để n2 là ước của (n 1)! +1, có hai giá trị n = 13 và n = 563, các giá trị khác chưa biết và tập hợp các giá trị n như thế có hữu hạn không cũng còn để mở, bao gồm các lệnh từ 5 đến 11.

Nhóm 3: Tìm giá trị của n để (n 1)! +1 là số chính phương, khi n = 5,68 thì (n 1)! + 1 là số chính phương, đó là bình phương của 5,11 và 71. Không rõ là còn các giá trị khác của n không? Maple đã kiểm tra với n = 9,10, ..., 100, f(n) = (n 1)! +1 không là số chính phương, chỉ có f(78) là số nguyên tố, với 114 chữ số, bao gồm các lệnh từ 12 đến 22.

Xem chương trình Sohoc5 sau đây:

>f:=n>(n1)!+1: (lệnh 1)

>map(f,[1,2,3,4,5,6,7,8,9]); (lệnh 2)



[2, 2, 3, 7, 25, 121, 721, 5041, 40321]

>e:=(((n1)!+1)/n^2)<1: (lệnh 3)

>type(e,"<"); (lệnh 4)

false

>f(13); (lệnh 5)

479001601

>ifactor(%); (lệnh 6)

(13)2(2834329)

>a:=f(563); (lệnh 7)

a:=1128062…3769781248000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

>length(a); (lệnh 8)



1304

>b:=a/563; (lệnh 9)

b:=2003662…630550621669627

>b*563; (lệnh 10)

112806210265…73769781248000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

>length(%); (lệnh 11)



1304

>c:=f(9); (lệnh 12)



c:= 40321

>sqrt(c); (lệnh 13)



>isprime(c); (lệnh 14)



false

>c:=f(78); (lệnh 15)

c:=145183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000001

>sqrt(c); (lệnh 16)

sqrt(145183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000001)

>isprime(c); (lệnh 17)



true

>c:=f(100); (lệnh 18)

c:=933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000001

>sqrt(c); (lệnh 19)

sqrt:=(933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000001)

>isprime(c); (lệnh 20)



false

>c:=f(78): (lệnh 21)

>length(c); (lệnh 22)

114

Lời giải: Dễ dàng thử lại rằng n = 5 thoả mãn hệ thức (n 1)! +1 = n2, các giá trị n = 2, 3 và 4 đều không thoả mãn. Với n = 6 ta có n2 > 6n  4. Bằng quy nạp ta chứng minh rằng bất đẳng thức (n 1)! + 1 > n2 đúng với mọi số tự nhiên lớn hơn hoặc bằng 6.

Nếu n là số tự nhiên lớn hơn 6, ta có:

(n 1)! + 1 > 2(n  1)(n 2) = 2(n2 3n + 2) > n2n2 > 6n  4.

Vậy với các số tự nhiên n > 5, đẳng thức (n 1)! + 1 = n2 không còn đúng.



2. SỐ NGUYÊN TỐ

Xác định “công thức” cho số nguyên tố là bài toán có ý nghĩa trong lịch sử toán học. Nhà toán học người Pháp Pie-Đơ-Phecma (Pierre De Fermat, 16011665) đưa ra công thức: fn = 22 + 1, với n = 0, 1, 2, 3, 4 ta được các số: 3, 5, 17, 257, 65537 đều là số nguyên tố. Nhưng vào năm 1732, Ơ-le (17071783) chỉ ra rằng f5 = 4294967297 = 641. 6700417 là hợp số. Có một chứng minh rất đơn giản (của Ben-nét, phiên âm theo tiếng Nga) như sau:



f5 = 2+ 1 = 232 + 1 = (2. 27)4 + 1.

Đặt a = 27b = 5, khi đó f5 = (2a)4 +1 = 24a4 + 1.

Mặt khác, 24 = 1 + 3b hay là 24 = 1+ b(ab3).

Suy ra f5 = (1 + abb4)a4 + 1 = (1 + ab)[a4 + (1  ab)(1 + a2b2)] và (1 + ab) là ước số của f5, với 1 + ab = 641.

Vấn đề đặt ra là liệu có còn những giá trị khác của n để fn là số nguyên tố? Tập hợp số nguyên tố đó có vô hạn không?

Sau đây là kết quả tính trên Maple V, với n = 6,7,..., 20 chỉ được toàn hợp số.



fn

Số chữ số

Giá trị

f6

20

(67280421310721).(274177)

f7

39

(5704689200685129054721).(59649589127497217)

f8

78

11579… 39937

f9

155

13407…84097

f10

309

17976…37217

f11

617

3231…30656

f12

1234

10443…90336

f13

2467

10907…92896

f14

4933

11897…66816

f15

9865

14154…77856

f16

19729

20035…56736

f17

39457

40141…73696

f18

78914

16113…00416

f19

157827

25963…73056

f20

315653

67411…79137

Ta có nhận xét sau: để phân tích f7 thành hai thừa số nguyên tố, Maple làm trong khoảng 15 phút. Tính số chữ số của f20 vượt ngoài khả năng của phiên bản Maple V dùng cho học sinh.

Đặt L(n) là số chữ số của fn, với n = 6, 7, …, 20 thì khi n = 8, 12, 18 thì L(n) = 2L(n  1), với các giá trị n còn lại thì L(n) = 2L(n 1)  1.

Các hợp số f5, f6, f7 đều phân tích thành hai thừa số nguyên tố có giá trị rất lớn, cho nên ở thế kỉ 18 việc chỉ ra rằng các số đó không là nguyên tố chẳng phải việc dễ dàng!

Xét số có dạng đơn giản hơn, số Fecma: gn = n2 + 1, với câu hỏi tương tự là với giá trị nào của n, các số đó là nguyên tố? Tập hợp các số nguyên tố đó có vô hạn không? Giải bằng Maple cho ta kết quả: n trong khoảng từ 104 đến 986 có ít nhất là 10 số nguyên tố. Khi n > 10 ta chỉ cần tính gn với n là số có chữ số tận cùng là 4 hoặc 6.

Với số có dạng hn = n! +1, ta cũng có câu hỏi tương tự.

Hai bài toán cuối cùng này do Đa-vit A Tô-mát (David A. Thomas) nêu ra trong cuốn “Những bài toán của thời đại máy tính” (tiếng Anh, xuất bản năm 1995).



Theo các công thức trên, ta thử lập bảng trong đó g có 10 giá trị là nguyên tố, h có 3 giá trị là hợp số và 6 giá trị là nguyên tố.

gn

Giá trị

hn

Kết quả

g116

13457

h2

3 – nguyên tố

g224

50177

h3

7 – nguyên tố

g236

55697

h11

39916801 – nguyên tố

g256

65537

h27

10888869450418352160768000001 – nguyên tố

g264

69697

h37

13763... 00001 có 44 chữ số – nguyên tố

g384

147457

h47

25862……….. 00001 có 60 chữ số – nguyên tố

g936

876097

h77

145……….. 01 có 114 chữ số – hợp số

g946

894917

h127

có 214 chữ số – hợp số

g966

933157

h137

có 235 chữ số – hợp số

g986

972197







Các bài toán này tuy rất đơn giản nhưng lại là những thách thức với người hâm mộ toán !
Каталог: ebooks
ebooks -> BÀi giảng hóa học vô CƠ Người soạn : ĐẶng kim triếT
ebooks -> Riêng về tin học, với tốc độ phát triển tính từng này, đã là một đề tài sôi động trên thế giới. Hầu hết báo chí các nước ngày nào cũng đều ít nhiều đề cập đến lĩnh vực này
ebooks -> TỔng quan về du già HÀnh tôNG
ebooks -> Lý thuyết viễn thông Hệ thống viễn thông điện tử 1 Hệ thống viễn thông điện tử ngày nay
ebooks -> Thiền Viện Thường Chiếu
ebooks -> 500 CÂu hỏi trắc nghiệm cơ BẢn về chứng khoán và thị trưỜNG chứng khoán câu L
ebooks -> Ns. Trí Hải dịch (1998) Nguyên tác: "What The Buddha Taught"
ebooks -> Bài Giảng Cuối Cùng (phần 1)
ebooks -> 2 kênh ide/ata
ebooks -> Thế giới Phẳng

tải về 105.27 Kb.

Chia sẻ với bạn bè của bạn:




Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý

    Quê hương