[perl]콜라츠 추측(3n+1)

2007-01-10   //   alexken작성   //   기술  //  No Comments

콜라츠 추측 (Collatz conjecture)은 1937년에 처음으로 이 추측을 제기한 로타르 콜라츠의 이름을 딴 것으로 3n+1 추측, 울람 추측, 혹은 헤일스톤(우박) 수열 등 여러 이름으로 불린다. 콜라츠 추측은 임의의 자연수가 다음 조작을 거쳐 항상 1이 된다는 추측이다.

짝수라면 2로 나눈다.
홀수라면 3을 곱하고 1을 더한다.
1이면 조작을 멈추고, 1이 아니면 첫 번째 단계로 돌아간다.

무지 간단해 보이는 데 타이틀 까지 건 이유가 뭔지 궁금해 호기심에서 짜 보았다.
게다가 정말 간단해 보이는데 이문제가 NP 문제라는게 더욱이 그러했다.

내가 짠 perl code는 이렇다. (짜는데야 타이핑 시간 1분여가 소요되었지만, 원 문제를 곱씹어 보면서 영어 해석하는데 좀 시간이 걸렸다. 쉽다고 댐볐지만, 내용의 깊이는 그리 간단한게 아니었다.)

#!/usr/bin/perl
use strict;

sub three_n_plus_one($){
  my ($n) = @_;
  print $n . " ";
  exit 0 if $n == 1;

  if($n % 2 == 1){
    three_n_plus_one(3 * $n + 1);
  }else{
    three_n_plus_one( $n2 );
  }
}

sub main(){
  three_n_plus_one(22);
}

main();

문제의 특징은:

  • 가정: 자연수를 주면 반드시 끝난다.
  • 간단해 보이는 알고리즘에도 불구하고, 이 가정이 사실인지는 알려져있지 않다.(아직은??? 영원히…)
  • 0 < n < 1,000,000사이에서는 그렇다는게 알려져 있다.

이정도???….

여러 숫자를 넣어 보니, 원 글에서 처럼,
… 5 16 8 4 2 1 로 수렴하며 끝나긴 끝났다.

참고로, 입력이 1,000,000,000,000,000였을 때
결과는

1e+15 500000000000000 250000000000000 125000000000000 62500000000000
31250000000000 15625000000000 7812500000000 3906250000000 1953125000000
976562500000 488281250000 244140625000 122070312500 61035156250 30517578125
91552734376 45776367188 22888183594 11444091797 34332275392 17166137696
8583068848 4291534424 2145767212 1072883606 536441803 1609325410 804662705
2413988116 1206994058 603497029 1810491088 905245544 452622772 226311386
113155693 339467080 169733540 84866770 42433385 127300156 63650078 31825039
95475118 47737559 143212678 71606339 214819018 107409509 322228528 161114264
80557132 40278566 20139283 60417850 30208925 90626776 45313388 22656694
11328347 33985042 16992521 50977564 25488782 12744391 38233174 19116587
57349762 28674881 86024644 43012322 21506161 64518484 32259242 16129621
48388864 24194432 12097216 6048608 3024304 1512152 756076 378038 189019
567058 283529 850588 425294 212647 637942 318971 956914 478457 1435372
717686 358843 1076530 538265 1614796 807398 403699 1211098 605549 1816648
908324 454162 227081 681244 340622 170311 510934 255467 766402 383201
1149604 574802 287401 862204 431102 215551 646654 323327 969982 484991
1454974 727487 2182462 1091231 3273694 1636847 4910542 2455271 7365814
3682907 11048722 5524361 16573084 8286542 4143271 12429814 6214907 18644722
9322361 27967084 13983542 6991771 20975314 10487657 31462972 15731486
7865743 23597230 11798615 35395846 17697923 53093770 26546885 79640656
39820328 19910164 9955082 4977541 14932624 7466312 3733156 1866578 933289
2799868 1399934 699967 2099902 1049951 3149854 1574927 4724782 2362391
7087174 3543587 10630762 5315381 15946144 7973072 3986536 1993268 996634
498317 1494952 747476 373738 186869 560608 280304 140152 70076 35038
17519 52558 26279 78838 39419 118258 59129 177388 88694 44347 133042
66521 199564 99782 49891 149674 74837 224512 112256 56128 28064 14032
7016 3508 1754 877 2632 1316 658 329 988 494 247 742 371 1114 557 1672
836 418 209 628 314 157 472 236 118 59 178 89 268 134 67 202 101 304
152 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

아!! 정말 영원히 풀 수 없는 문제란 말인가???