페린수

수학에서 Perrin 숫자는 반복 관계에 의해 정의됩니다.

P (n)

=

P (n - 2)

+

P (n

-

3

) (n >

2

의

경우

),

초기값과 함께

P (0) = 3, P

(1

) = 0, P

(2)

=

2

.

Perrin 번호의 시퀀스는 다음과 같이 시작합니다.

3, 0, 2, 3, 5, 7, 10, 12, 17, 22, 29, 39, ...(OEIS의 시퀀스 A001608)

n-vertex 사이클 그래프에서 서로 다른 최대 독립 집합의 수는 n > ^[1]^{[page needed]} $1$ 에 $대한$ n번째 Perrin 수로 계산됩니다.

역사

이 순서는 에두아르 루카스 (1876년)에 의해 암묵적으로 언급되었다.1899년 프랑수아 올리비에 라울 ^[2]^{[page needed]}페랭에 의해 같은 순서가 명시적으로 언급되었다.이 시퀀스에 대한 가장 광범위한 치료는 애덤스와 샹크스(1982)에 의해 이루어졌다.

특성.

생성함수

Perrin 시퀀스의 생성 함수는

({displaystyle G(n);x)=param frac {3-x^{2}}{1-x^{2}-x^{3}}).}

행렬식

{begin {pmatrix} 0&1&0&1&1&0\end {pmatrix}{n}{\begin {pmatrix}3\\\2\end {pmatrix}=begin {pmatrix}P\left(n\오른쪽)\\\\\\begin {pmatrix}P\left(n+1\오른쪽)\\P\left(n+2\right)\end{pmatrix}

비넷유사식

Perrin 시퀀스를 따르는 변 길이가 있는 정삼각형 나선형입니다.

Perrin 시퀀스 번호는 방정식의 근의 거듭제곱으로 쓸 수 있습니다.

(\displaystyle x^{3}-x-1=0).}

이 방정식은 3개의 루트를 가지고 있습니다.하나의 실제 루트 p(플라스틱 번호)와 2개의 복소공역 루트 q와 r입니다.이 세 개의 뿌리가 주어졌을 때, 루카스 배열 비넷 공식의 페린 배열 유사체는 다음과 같다.

P\left(n\right)={p^{n}+{q^{n}}+{r^{n}}}.

복소근 q와 r의 크기가 둘 다 1보다 작기 때문에 이들 근의 거듭제곱은 n이 클 때 0에 접근합니다.n이 클 경우 공식은 다음과 같이 감소한다.

P\left(n\right)\약 {p^{n}

이 공식을 사용하여 큰 n에 대한 Perrin 시퀀스 값을 빠르게 계산할 수 있습니다.페린 수열의 연속 항 비율은 p, 즉 플라스틱 번호에 근접하며, 값은 약 1.324718입니다.이 상수는 황금 비율이 루카스 수열과 같은 페린 수열과 관련이 있습니다.p와 Padovan 시퀀스 간, 황금 비율과 피보나치 수 간, 은 비율과 Pell 수 간에도 유사한 연결이 존재합니다.

곱셈 공식

비넷 공식에서 G(n-1), G(n) 및 G(n+1)의 관점에서 G(kn)에 대한 공식을 얻을 수 있다.

{ begin { matrix }G(n-1)&=&p^{-1}q^{n}+&r^{n}\G(n)&=&p^{n}+&p^{n}+&p^{n}&p^{n}+&p^{n}&p^{n}&p^{n

x $x^{3}-x-1$ - $x^{3}-x-1$ - $({$ $displaystyle$ x $^{3}-x-1$ 의 $x^{3}-x-1$ 필드에 대한 계수를 갖는 세 개의 선형 방정식을 제공합니다. 행렬을 반전시키면 $p^{n},q^{n},r^{n}$ $,$ $p^{n},q^{n},r^{n}$ n, $r$ , $r^{n}$ 에 $p^{n},q^{n},r^{n}$ $p^{n},q^{n},r^{n}$ 풀 수 있으며 k제곱으로 올리고 합계를 계산할 수 있습니다.

마그마 코드의 예:

P <x> := 다항식링(Rationals()), S <t> := 분할필드(x^3-x-1), P2 <y> := 다항식링(S), p,q,r := 폭발([r[1] : r in Roots(y^3-y-1));Mi: = Ring([1/p,1/q,1/r],[1,1,1],[p,q,r])^(-1), T <u,v,w> := 다항식링(S,3); v1 : = 변경링(Mi,T) *행렬(w,r)

그 결과 $u=G(n-1),v=G(n),w=G(n+1)$ $u=G(n-1),v=G(n),w=G(n+1)$ G ( $u=G(n-1),v=G(n),w=G(n+1)$ - $u=G(n-1),v=G(n),w=G(n+1)$ ), $u=G(n-1),v=G(n),w=G(n+1)$ $u=G(n-1),v=G(n),w=G(n+1)$ ( $u=G(n-1),v=G(n),w=G(n+1)$ $u=G(n-1),v=G(n),w=G(n+1)$ $u=G(n-1),v=G(n),w=G(n+1)$ $u=G(n-1),v=G(n),w=G(n+1)$ ( $u=G(n-1),v=G(n),w=G(n+1)$ + $u=G(n-1),v=G(n),w=G(n+1)$ $){$ $displaystyle$ u $= G$ ( $n-1),$ v $= G$ ( $n($ n), w $= G$ ( $n+1$ 가 있는 $u=G(n-1),v=G(n),w=G(n+1)$ ,

{\displaystyle{\begin{행렬}(2n-1)&, =&, 4u^ᆯ+3v^ᆰ+9w^ᆱ+18uv-12uw-4vw\\23G(2n)&, =&, -6u^ᆲ+7v^ᆳ-2w^ᆴ-4uv+18uw+6vw\\23G(2n+1)&, =&, 9u^ᆵ+v^ᆶ+3w^ᆷ+6uv-4uw+14vw\\23G(3n-1)&, =&, \left(-4u^{3}+2v^{3}-w^{3}+9(uv^{2}+vw^{2}+wu^{2})+3v^{2}w+6uvw\right)\\23G(3n)&, =&, \left(3u^{3}+2v^{3}+3w^{3}-3(uv^{2}+uw^{2}+vw^{2}+vu^{2})+6v^{2}w+18uvw\right)\\23G(3n+1)&\left(v^{3}-w^{2}+6uv^{2}+9uw^{2}+9uw^{2}-3wu^{2}+6uv^{2}-6uvw\오른쪽)\end{w}}

여기서 숫자 23은 수열의 정의 다항식의 판별식에서 비롯된다.

이를 통해 O $O(\log n)$ ( $O(\log n)$ n $O(\log n)$ ) { $displaystyle$ O $(\log$ n $)}$ 의 $O(\log n)$ 정수연산을 사용하여 n번째 Perrin 수를 계산할 수 있습니다.

소수점 및 약수

페린 의사 소수

모든 소수 p에 대해 p는 P(p)를 나눈다는 것이 증명되었다.단, 그 반대는 사실이 아닙니다.일부 합성수 n의 경우 n은 여전히 P(n)를 나눌 수 있습니다.n이 이 속성을 가질 경우 Perrin pseudoprime이라고 합니다.

처음 몇 개의 Perrin 유사 소수는 다음과 같습니다.

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 1026901, 130949, 196075949, 214038533, 517697641, 5456703, 801123451, 855073301, 903131, 9354 시퀀스...

페린의 존재에 대한 질문은 페린이 직접 고려했지만 아담스와 샹크스가 가장 작은 271441 = 521을² 발견할 때까지 존재 여부는 알려지지 않았다. 다음 숫자는 904631 = 7 x 13 x 9941이다.그들 ^[3]중 10억보다 적은 17개가 있다; 존 그랜섬은 Perrin 유사소수가 무한히 많다는 것을 증명했다^[4].

애덤스와 샹크스(1989)는 소수가 P(-p) = -1 mod p라는 조건도 충족한다고 언급했다.두 특성이 모두 유지되는 복합물을 "제한된 Perrin 의사소수(Restricted Perrin pseudoprimes)"라고 합니다(OEIS의 시퀀스 A018187).추가 조건은 3가지 형식 중 하나여야 하는 6가지 요소 시그니처를 사용하여 적용할 수 있습니다(예: OEIS: A275612 및 OEIS: A275613).

페린 의사소수는 드물지만 페르마 의사소수와 상당히 겹친다.이것은, 반상관성이 있는 Lucas 의사 소수점과는 대조적입니다.후자의 조건을 부정 이용하는 것으로, 기존의 의사 소수가 없고, 최소가 2보다⁶⁴ 큰 것으로 알려진, 널리 사용되고, 효율적이며, 보다 효과적인 BPSW 테스트가 실현됩니다.

페린 소수

페린 소수는 소수인 페린 수이다.처음 몇 개의 Perrin 소수는 다음과 같습니다.

2, 3, 5, 7, 29, 277, 367, 853, 14197, 43721, 1442968193, 79260655539797, 187278591804172321, 662411604887801471579864797... (OEIS의 시퀀스 A074788)

이러한 Perrin 소수에서 P $(n)$ 의 지수 n은

2, 3, 4, 5, 7, 10, 12, 20, 21, 24, 34, 38, 75, 122, 166, 235, 356, 930, 1041+1, 1214, 1461, 1622, 4430, 5802, 9092, ...(OEIS의 시퀀스 A112881).

여기서 n은 음의 정수인 P(n)를 생성하면 primality에 관한 유사한 특성이 생성됩니다.n이 음의 경우 P(n) mod -n = -n - 1일 때 P(n)는 prime입니다.다음 시퀀스는 음의 정수인 모든 n에 대해 P(n)를 나타냅니다.

-1, 1, 2, -3, 4, -2, -1, 5, -7, 6, -1, -6, -6, -1, 12, -13, 7, 5, -18, 25, -20, 2, 23, -43, 45, -22, -21, 66, -88, 67, -1, ... (OEIS의 시퀀스 A078712)

메모들

^ 휘레디(1987년)
^ Knuth (2011)
^ (OEIS의 시퀀스 A013998)
^ Jon Grantham (2010). "There are infinitely many Perrin pseudoprimes" (PDF). Journal of Number Theory. 130 (5): 1117–1128. arXiv:1903.06825. doi:10.1016/j.jnt.2009.11.008.

레퍼런스

Füredi, Z. (1987). "The number of maximal independent sets in connected graphs". Journal of Graph Theory. 11 (4): 463–470. doi:10.1002/jgt.3190110403.

Knuth, Donald E. (2011). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley. ISBN 0201038048.

추가 정보

Adams, William; Shanks, Daniel (1982). "Strong primality tests that are not sufficient". Mathematics of Computation. American Mathematical Society. 39 (159): 255–300. doi:10.2307/2007637. JSTOR 2007637. MR 0658231.

Perrin, R. (1899). "Query 1484". L'Intermédiaire des Mathématiciens. 6: 76.

Lucas, E. (1878). "Théorie des fonctions numériques simplement périodiques". American Journal of Mathematics. The Johns Hopkins University Press. 1 (3): 197–240. doi:10.2307/2369311. JSTOR 2369311.

외부 링크

Zentrum für Hirnforschung Institut für Medizinische Kybernetik und 인공지능
"Lucas Pseudoprimes". MathPages.com.
"Perrin's Sequence". MathPages.com.
OEIS 시퀀스 A225876(s(n)+1을 나누는 합성n, 여기서 s는 ...): 페린 계열의 시퀀스
Perrin 프라이머리 테스트

[1] 휘레디(1987년)

[2] Knuth (2011)

[3] (OEIS의 시퀀스 A013998)

[4] Jon Grantham (2010). "There are infinitely many Perrin pseudoprimes" (PDF). Journal of Number Theory. 130 (5): 1117–1128. arXiv:1903.06825. doi:10.1016/j.jnt.2009.11.008.

[1]

[2]

[3]

[4]

v t 소수 클래스
공식에 의한	페르마 ( $2 2 n$ + $1$ ) 메르센 $(2 p$ - 1) $더블 2 p -1$ 메르센(2 - $1$ ) 와그스태프( $2 p +1)/3$ 프로스( $k \cdot2 n$ + $1$ ) 요인( $n!$ ± $1$ ) 초기( $p n #$ ± $1$ ) 유클리드( $p n #$ + $1$ ) 피타고라스어 ( $4n$ + $1$ ) 피어폰트( $2 m \cdot3 n +1$ ) 쿼탄( $x 4$ + $y 4$ ) 솔리나(2 ± $2 m$ ± $1 n$ ) Cullen ( $n \cdot2 n + 1$ ) 우돌( $n \cdot2 n$ - $1$ ) 쿠바어( $x 3$ - $y 3)/(x$ - $y$ ) 레이랜드 ( $x y$ + $y x$ ) Thabit ( $3\cdot2 n - 1$ ) 윌리엄스(( $b-1)\cdotb-1 n$ ) 밀스( $A 3 n)$
정수순서별	피보나치 루카스 펠 뉴먼 생크스 윌리엄스 페린 파티션 벨 모츠킨
속성별	비페리히(페어) 벽-태양-태양 볼스텐홀름 윌슨 럭키 행운의 라마누잔 필라이 규칙적인. 강한. 스턴 슈퍼싱귤러(엘리전트 곡선) 초대칭(문신 이론) 좋아요. 잘 하는 군요 힉스 고공역성
베이스 의존	회문 에미르프 유닛 $(10 n$ - $1)/9$ 치환 가능 원형 잘라낼 수 있다 최소 연약한 원시 전체 파충류 독특한 행복해 자신 스마란다슈웰린 스트로보그라마틱 이면체 테트라디크
패턴	트윈 ( $p, p$ + $2$ ) 쌍방향 체인( $n \pm 1$ , $2n \pm 1$ , $4n \pm 1$ , $\dots)$ 삼중항( $p, p$ + 2 $또는$ p + $4,$ p + $6$ ) 4중항( $p, p$ + 2 $, p$ + $6,$ p + $8$ ) k태플 사촌 ( $p, p$ + $4$ ) 섹시 ( $p, p$ + $6$ ) 첸 Sophie Germain / Safe ( $p, 2p$ + $1$ ) 커닝햄( $p, 2p \pm 1$ , $4p \pm 3$ , $8p$ $\pm 7$ , $...)$ 산술 수열( $p$ + $a\cdotn,$ $n$ = $0, 1, 2, 3$ , $...)$ 밸런스( $연속$ p - $n,$ $p, p$ + $n$ )
크기별	메가(1,000,000자리 이상) 알려진 최대 크기
복소수	아이젠슈타인 소수 가우스 프라임
합성수	의사 시간 카탈로니아어 타원형 오일러 오일러-야코비 페르마 프로베니우스 루카스 소머-루카스 강한. 카마이클 수 거의 프라임 세미프라임 인터프라임 유해.
관련 토픽	개연소수 산업용 프라임 부정한 소수 소수 공식 프라임 갭
처음 60개의 소수점	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
소수 목록

Search

페린수

네임스페이스

더

목차

역사

특성.