유사소수

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

유사 소수(pseudo primes)는 불완전하나마 소수를 생성해내는 생성함수를 지칭한다. 또는 그러한 생성함수를 통해서 만들어지는 소수를 말한다. 의사소수로도 불린다. 그러나 생성함수 그 자체로는 불완전한것이 아니다.

종류[편집]

  • 카탈랑 유사소수(Catalan pseudoprime)
음이 아닌 정수 n 에 대해서, n 번째 카탈랑 수 는 다음과 같다.
카탈랑 수는 자연수열이며, n = 0…37 까지의 값들은 아래와 같다. (OEIS의 수열 A000108)
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304, 14544636039226909, 55534064877048198, 212336130412243110, 812944042149730764, 3116285494907301262, 11959798385860453492, 45950804324621742364, …
  • 오일러 유사소수(Euler pseudoprime)
서로소
  • 오일러-야코비 유사소수(Euler–Jacobi pseudoprime)
야코비 기호


  • 루카스 유사소수(Lucas pseudoprime)
그리고,
루카스 수열 에 대응하는
자연수 , 야코비 기호


  • 페린 유사소수(Perrin pseudoprime)
초기 몇몇의 값은 다음과 같다.

함께보기[편집]