多項式ではないもの（漸化式）では・・・

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】フランクの漸化式

　　ａn＝ａn-1＋ＧＣＤ（ｎ，ａn-1），ａ1＝７

　　ＧＣＤ：最大公約数

　早速簡単な検証に移るが，ｎ＝２のとき，ａ1＝７より，

　　ａ2＝７＋ＧＣＤ（２，７）＝７＋１＝８

　　ａ3＝８＋ＧＣＤ（３，８）＝８＋１＝９

　　ａ4＝９＋ＧＣＤ（４，９）＝９＋１＝１０

　　ａ5＝１０＋ＧＣＤ（５，１０）＝１０＋５＝１５

　　ａ6＝１５＋ＧＣＤ（６，１５）＝１５＋３＝１８

　　ａ7＝１８＋ＧＣＤ（７，１８）＝１８＋１＝１９

　　ａ8＝１９＋ＧＣＤ（８，１９）＝１９＋１＝２０

　　ａ9＝２０＋ＧＣＤ（９，２０）＝２０＋１＝２１

　　ａ10＝２１＋ＧＣＤ（１０，２１）＝２１＋１＝２２

　　ａ11＝２２＋ＧＣＤ（１１，２２）＝２２＋１１＝３３

　　ａ12＝３３＋ＧＣＤ（１２，３３）＝３３＋３＝３６

　　ａ13＝３６＋ＧＣＤ（１３，３６）＝３６＋１＝３７

　　ａ14＝３７＋ＧＣＤ（１４，３７）＝３７＋１＝３８

　　ａ15＝３８＋ＧＣＤ（１５，３８）＝３８＋１＝３９

　　ａ16＝３９＋ＧＣＤ（１６，３９）＝３９＋１＝４０

　　ａ17＝４０＋ＧＣＤ（１７，４０）＝４０＋１＝４１

　　ａ18＝４１＋ＧＣＤ（１８，４１）＝４１＋１＝４２

　　ａ19＝４２＋ＧＣＤ（１９，４２）＝４２＋１＝４３

　　ａ20＝４３＋ＧＣＤ（２０，４３）＝４３＋１＝４４

　　ａ21＝４４＋ＧＣＤ（２１，４４）＝４４＋１＝４５

　　ａ22＝４５＋ＧＣＤ（２２，４５）＝４５＋１＝４６

　　ａ23＝４６＋ＧＣＤ（２３，４６）＝４６＋２３＝６９

　　ａ24＝６９＋ＧＣＤ（２４，６９）＝６９＋３＝７２

　　ａ25＝７２＋ＧＣＤ（２５，７２）＝７２＋１＝７３

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　　ａ5＝１０＋ＧＣＤ（５，１０）＝１０＋５＝１５

　　ａ6＝１５＋ＧＣＤ（６，１５）＝１５＋３＝１８

　　ａ11＝２２＋ＧＣＤ（１１，２２）＝２２＋１１＝３３

　　ａ12＝３３＋ＧＣＤ（１２，３３）＝３３＋３＝３６

　　ａ23＝４６＋ＧＣＤ（２３，４６）＝４６＋２３＝６９

　　ａ24＝６９＋ＧＣＤ（２４，６９）＝６９＋３＝７２

　したがって，

　　ＧＣＤ（ｎ，ａn-1）≠１のとき，

　　ＧＣＤ（ｎ，ａn-1）＝３ｎ

が容易に確かめられる．

　ａn−ａn-1＝ＧＣＤ（ｎ，ａn-1）は

［１］１または素数．

［２］素数ｐが生成される前に１が（ｐ−３）／２個続く．

［３］ａ1＝７でない場合，合成数を生成することがある．

［４］ｐ＝２は生成されない．

［５］無限に多くの異なる素数を生成する．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝