\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{times}
%\usepackage{ifpdf}
\usepackage{makeidx}
\usepackage{graphicx}

\newtheorem{rem}{Remark}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}
\newcommand{\Q}{{\mathbb{Q}}}
\newcommand{\atan}{{\mbox{atan}}}
%\newcommand{\faux}{$\square\;$}
%\newcommand{\vrai}{$\square\;$}
%\newtheorem{thm}{Theorem}
%\newtheorem{exo}{Exercice}[section]
\input{giac.tex}
\giacmathjax
\title{La spirale des nombres premiers de Ulam avec la tortue}
\author{Ren\'ee De Graeve}
\date{2018}
\begin{document}
\begin{giacjshere}
\maketitle
\tableofcontents
\newpage
\section{Introduction}
En 1963, lors d'une communication ennuyeuse Stanislas M. Ulam de l'universit\'e 
de Los Alamos \'ecrit les entiers naturels selon une spirale, et il entoure
les nombres premiers. \`A sa grande surprise 
il obtient beaucoup d'alignements.\\
Nous allons faire faire \`a la tortue ce qu'a fait  Stanislas M. Ulam :
\begin{enumerate}
\item Le dessin d'une spirale, 
\item L'\'ecriture des entiers $k_0,k_0+1...K$ selon une spirale ($k_0\geq 1$), 
\item Rep\'erer dans la spirale, les nombres premiers par un carr\'e rouge, 
\item Rep\'erer dans la spirale, les nombres premiers jumeaux par un carr\'e bleu.
\end{enumerate}
\section{Le dessin d'une spirale}
une spirale est form\'e de spires qui sont les 2 c\^ot\'es contig\"us d'un 
carr\'e.\\
Voici le programme qui r\'ealise le dessin d'une spirale ayant $p$ spires dont 
les dimensions vont de $n$ jusqu'\`a $p*n$.
\begin{giaconload}
fonction spirale(p,n=10)
  local k;
  recule n; tourne_droite 90;
  avance n,tourne_gauche 90;
  pour k de 2 jusque p faire
  repete (2,avance k*n,tourne_gauche 90);
fpour;
ffonction:;
\end{giaconload}
\giacinputbig{efface;saute 30;pas_de_cote 30;spirale(20,10)}

\section{Les proc\'edures utiles pour \'ecrire les nombres $k_0,k_0+1...K$ selon une spirale}
\subsection{Les polygones r\'eguliers}
D\'efinir une proc\'edure {\tt isopoly(p,n)} qui trace un polygone r\'egulier 
de c\^ot\'e de longueur $n$ et ayant $p$ sommets.
\begin{giaconload}
fonction isopoly(p,n)
  repete(p,avance n,tourne_gauche 360/p);
ffonction:;
\end{giaconload}
\giacinputbig{efface;pas_de_cote -50; isopoly(3,100);isopoly(4,100);isopoly(5,100);isopoly(6,100);}

\subsection{La proc\'edure {\tt ecrisdans(a,n)}}
\`A chaque position de la tortue, on appelle carr\'e direct-$n$, le carr\'e de 
c\^ot\'e $n$ que peut d\'ecrire la tortue.\\
D\'efinir une proc\'edure {\tt ecrisdans(a,n)} qui \'ecrit au centre de ce 
carr\'e.\\
On utilisera l'instruction {\tt ecris(a,b)} qui \'ecrit {\tt a} avec la fonte 
{\tt b} (par d\'efaut {\tt b=14}) \`a l'endroit o\`u
se trouve la tortue sans tenir compte de son orientation ({\tt a} est soit une 
cha\^{i}ne, soit un nombre, soit un nom de variable contenant une cha\^{i}ne ou
 un nombre).
\begin{giaconload}
fonction ecrisdans(a,n=15,b=14)
  pas_de_cote n/2;
  saute n/2;
  ecris(a,b);
  saute -n/2;
  pas_de_cote -n/2;
ffonction:;
\end{giaconload}
Pour voir la diff\'erence entre {\tt ecrisdans} et {\tt ecris} :\\
\giacinputbig{efface;repete(4,isopoly(4,50),ecrisdans(1,50,20),avance 100,tourne_gauche 90);saute 150;ecrisdans("fin",50,20)}\\
\giacinputbig{efface;repete(4,isopoly(4,50),ecris(1,20),avance 100,tourne_gauche 90);saute 150;ecrisdans("fin",50,20)}\\
On tape par exemple :\\
\giacinputbig{efface;pour k de 1 jusque 4 faire isopoly(4,50);ecrisdans(100*k,50,10);avance 100;tourne_gauche 90;fpour;}

\subsection{La proc\'edure {\tt carrentier(a,n)}}
D\'efinir la proc\'edure {\tt carrentier(a,n)} qui trace un carr\'e direct de 
c\^ot\'e {\tt n}, qui \'ecrit {\tt a} au centre de ce carr\'e puis qui saute de 
{\tt n} pour que la tortue soit  pr\^ete \`a \'ecrire l'entier suivant.
\begin{giaconload}
fonction carrentier(a,n=15,b=14)
  isopoly(4,n);
  ecrisdans(a,n,b);
  saute n;
ffonction:;
\end{giaconload}
\giacinputbig{efface;carrentier(1,30);carrentier(2,30);carrentier(3,30)}\\
\giacinputbig{efface;carrentier(1,30,10);carrentier(2,30,10);tourne_gauche;saute 30;carrentier(3,30,10)}

\section{Les nombres $k_0,k_0+1...K$ ($1\leq k_0\leq K$) dessinant une spirale}
On va tout d'abord d\'ecrire ce que l'on doit faire pour placer les nombres 
$1,2..10$ selon la spirale :\\
\giacinputbig{efface;spiralentier(1,13,30,10)}\\
On commence par \'ecrire {\tt 1} avec {\tt carrentier(1,n)} et gr\^ace \`a 
{\tt saute n} contenu dans {\tt carrentier(1,n,b)} on pourra \'ecrire {\tt 2}.\\
On \'ecrit {\tt 2} avec {\tt carrentier(2,n,b)} et gr\^ace \`a 
{\tt saute n} contenu dans {\tt carrentier(2,n,b)} la tortue se trouve dans 
un angle donc :\\
pour que {\tt 3} se trouve au dessus de {\tt 2}, la tortue doit tourner
\`a gauche et sauter, puis, on \'ecrit 3.\\
Gr\^ace \`a {\tt saute n} contenu dans {\tt carrentier(3,n,b)} la tortue se 
trouve \`a nouveau dans un angle donc :\\
pour que {\tt 4} se trouve \`a gauche de {\tt 3}, la tortue doit tourner
\`a gauche et sauter ....\\
{\bf D\'efinition}
Lorsque la tortue \'ecrit dans une suite de $p$ carr\'es les nombres 
$k,k+1,..k+p-1$  puis tourne \`a gauche et saute pour \'ecrire dans une suite 
de $p$ carr\'es,situ\'es au dessus du carr\'e $k+p-1$, les nombres 
$k+p,k+p1,..k+2p-1$ puis tourne \`a gauche et saute, on dit que la tortue a 
effectu\'e une {\bf spire} qui sera la proc\'edure {\tt spirentier(p,k,n,b)} 
({\tt n} donne la dimension du carr\'e et {\tt b} la taille de la fonte servant 
\`a \'ecrire $k$).\\ 
On tape pour faire la premi\`ere spire ({\tt p=1}) :\\
{\tt carrentier(2,n,b);tourne\_gauche; saute n;\\
carrentier(3,n,b);tourne\_gauche; saute n;}.\\
On appelle {\tt tgsa(n)} (abreviation tourne\_gauche saute n) (resp 
{\tt tgav(n)} (abreviation tourne\_gauche avance n)) la proc\'edure 
qui fait passer de l'\'ecriture de {\tt 2} \`a l'\'ecriture de {\tt 3}.\\
Puis pour faire la deuxi\`eme spire ({\tt p=2}) :\\
on \'ecrit {\tt 4,5}, {\tt tgsa(n)}, on \'ecrit {\tt 6,7},{\tt tgsa(n)} puis :\\
Puis pour faire la troisi\`eme spire ({\tt p=3}) :\\
on \'ecrit {\tt 8,9,10}, {\tt tgsa(n)}, on \'ecrit {\tt 11,12,13},{\tt tgsa(n)} etc ..\\
On appelle {\tt spirentier(p,k,n,b)} ({\tt p>=1}) la proc\'edure qui 
pour {\tt j}$\in${\tt [0,1...p-1]} ex\'ecute : 
{\tt carrentier(j+k,n,b); tgsa(n);} puis pour  
pour {\tt j}$\in${\tt [p,p+1...2p-1]} ex\'ecute 
{\tt carrentier(j+k,n,b); tgsa(n)}

\subsection{La proc\'edure {\tt spirentier(p,k,n,b)}}
On d\'efinit la proc\'edure {\tt spirentier(p,k,n,b)}
\begin{giaconload}
fonction tgsa(n=15)
  tourne_gauche;
  saute n;
ffonction:;
fonction tgav(n=15)
  tourne_gauche;
  avance n;
ffonction:;
fonction spirentier(p,k,n=15,b=12)
  local j;
  pour j de 0 jusque p-1 faire
    carrentier(j+k,n,b);
  fpour;
  tgsa(n);
  pour j de p jusque 2p-1 faire
    carrentier(j+k,n,b);
  fpour;
  tgsa(n);
ffonction:;
\end{giaconload}
Voici le d\'ebut de la spirale,le d\'epart en noir, la premi\`ere spire en 
rouge, la deuxi\'eme spire en vert avec les nombres \'ecrits avec une 
fonte de 12 :\\
\giacinputbig{efface;crayon 0;carrentier(1,30,12);crayon 1;spirentier(1,2,30,12);crayon 2;spirentier(2,2+2*1,30,12)}\\
Voici la suite de la spirale, la troisi\`eme spire en jaune, la quatri\'eme 
 en bleu, la cinqi\`eme  en magenta et la sixi\`eme en cyan avec les nombres
\'ecrits avec une fonte de 10):\\
\giacinputbig{crayon 3;spirentier(3,4+2*2,30);crayon 4;spirentier(4,8+2*3,30,10);crayon 5;spirentier(5,14+2*4,30,10);crayon 6;spirentier(6,22+2*5,30,10)}
\giacinputbig{efface;pas_de_cote -30;crayon 3;spirentier(3,4+2*2,30);crayon 4;spirentier(4,8+2*3,30,10);crayon 5;spirentier(5,14+2*4,30,10);crayon 6;spirentier(6,22+2*5,30,10)}

\subsection{La proc\'edure {\tt spiralentier(k0,K,n)}}
On d\'efinit la proc\'edure {\tt spiralentier(k0,K,n,b)} qui \'ecrit selon une 
spirale, les entiers $k_0 k_0+1...K$ lorsque $1\leq k_0\leq K$ :\\
\begin{giaconload}
fonction spiralentier(k0,K,n=25,b=6)
  local k,p;
  k:=k0;
  //ecrisdans(k,n);avance n;
  carrentier(k,n,b);
  p:=1;
  k:=k+1;
  tantque k<=K faire
    spirentier(p,k,n,b);
    k:=k+2*p;
    p:=p+1;
  ftantque;
  avance 0;
ffonction:;
\end{giaconload}
\giacinputbig{efface;saute 25;pas_de_cote 10;spiralentier(1,100,23,6)}\\
\giacinputbig{efface;saute 25;spiralentier(41,100,25,6)}\\

{\bf Remarque et exercice}\\
Si $K$ est un entier contenu de {\tt spirentier(p,k,n=15)}, montrer que 
{\tt spiralentier(k0,K,n,b)} \'ecrit selon une spirale, les entiers
$k_0..1+p*(p+1)$.\\ 
{\tt spiralentier(k0,K,n,b)} \'ecrit les entiers contenus dans une spire donc
{\tt spiralentier(k0,K,n,b)} \'ecrit selon une spirale, les entiers de $k_0$ 
jusqu'\`a $k_0+p*(p+1)$ si $(p-1)p+k_0<K \leq p(p+1)+k_0$.\\
Par exemple si :\\
$k_0=1$, $K=100$ on a $p=10$ car $9*10+1=91<100\leq 111=10*11+1$,
{\tt spiralentier(1,100,n,b)} \'ecrit selon une spirale, les entiers de 1 
juqu'\`a 111 .\\
$k_0=41$, $K=100$ on a $p=8$ car $7*8+41<97\leq 113=8*9+41$,
{\tt spiralentier(41,100,n,b)} \'ecrit selon une spirale, les entiers de 41 
juqu'\`a 113 .\\
Montrer que $p=${\tt ceil}$((-1+\sqrt{1+4(K-k0)})/2)$.\\ 
$k_0=1$ alors $p=${\tt ceil}$((-1+\sqrt{4K-3})/2)$.\\
\giacinput{K:=90;ceil((-1+sqrt(4*K-3))/2)}\\
\giacinput{K:=100;ceil((-1+sqrt(4*K-3))/2)}\\
\giacinput{K:=111;ceil((-1+sqrt(4*K-3))/2)}\\
Si $k_0=1$ et $K=100$ {\tt spiralentier(k0,K,n,b)} \'ecrit les entiers
de 1 jusque $111 =p*(p+1)+1$ car $p=10$.\\
Si $k_0=41$ et $K=100$ {\tt spiralentier(k0,K,n,b)} \'ecrit les entiers
de 41 jusque $113 =p*(p+1)+1$ car $p=8$.\\
Pour v\'erifier :\\
\giacinputbig{K:=100;p1:=ceil((-1+sqrt(1+4*(K-1)))/2);p0:=ceil((-1+sqrt(1+4*(K-41)))/2)}\\
\giacinputbig{p1*(p1+1)+1,p0*(p0+1)+41}\\
{\bf Correction}\\
Cherchons le dernier nombre $u_p$ de {\tt spirale(p,k0,n,b)}.\\)
On a :\\
$u_0=k_0$, $u_1=3=k_0+2*1$, $u_2=u_1+2*2=k_0+2*1+2*2$....$u_p=u_{p-1}+2*p$ donc \\
$u_p=k_0+2(1+2...p)=p(p+1)+k_0$ et $u_{p-1}=(p-1)p+1=p^2-p+k_0$.
Etant donn\'e un entier $K$ cherchons l'entier $p$ tel que :\\
$u_{p-1}<K \leq u_p$ i.e. $p^2-p<K-k_0 \leq p^2+p$.
Soient $x_1$ et $x_2$ ($x_1<0<x_2$) les racines de $P(x)=x^2+x+k_0-K=0$.
On a  $x_1=(-1-sqrt(1+4*(K-k_0)))/2$ et $x_2=(-1+sqrt(1+4*(K-k_0)))/2$.\\
Dire que  :\\
$p^2-p+k_0-K=f(p-1)<0$ veut dire que $p-1$ se trouve entre $x_1$ et $x_2$
$p^2+p+k_0-K=f(p)\geq 0$ veut dire, puisque $p>0$, que $p$ se trouve dans 
$[x_2 +\infty$ donc on a :\\
$p-1<x_2\geq p$ donc \\
$p$ est le plus petit entier sup\'erieur ou \'egal \`a  $x_2$ donc \\
$p=${\tt ceil}$(x_2)=${\tt ceil}$((-1+sqrt(1+4*(K-k_0)))/2)$.\\
Donc lorsque $1\leq k_0\leq K$, si $p==${\tt ceil}$((-1+sqrt(1+4*(K-k_0)))/2)$, 
la proc\'edure {\tt spiralentier(k0,K,n,b)} \'ecrit selon une spirale, 
les entiers $k_0 k_0+1...p(p+1)+k_0$.\\
\giacinputbig{efface;spiralentier(1,91,25,8)}\\
\giacinputbig{efface;spiralentier(41,83,30,10)}

\section{Exercice}
\'Ecrire les entiers de $k0$ jusque $K$ selon une spirale en ne dessinant 
que la spirale sans dessiner le contour des carr\'es par exemple :\\
\giacinputbig{efface;spiralentierexo(1,31,30,10)}\\

\begin{giaconload}
fonction tgav(n)
  tourne_gauche;
  avance n;
ffonction:;
fonction spirentierexo(p,k,n=25,b=8)
  local j;
  pour j de 0 jusque p-1 faire
    ecrisdans(j+k,n,b);avance n;
  fpour;
  tgav(n);
  pour j de p jusque 2p-1 faire
    ecrisdans(j+k,n,b);avance n;
  fpour;
  tgav(n);
ffonction:;
fonction spiralentierexo(k0,K,n=25,b=8)
  local k,p;
  k:=k0;
  //ecrisdans(k,n);saute n;
  carrentier(k,n,b);
  p:=1;
  k:=k+1;
  tantque k<=K faire
    spirentierexo(p,k,n,b)
    k:=k+2*p;
    p:=p+1;
  ftantque;
  avance 0;
ffonction:;
\end{giaconload}
\giacinputbig{efface;pas_de_cote 18;saute 20;spiralentierexo(1,100,22,6)}\\
\giacinputbig{efface;pas_de_cote 12;saute 20;spiralentierexo(41,100,27,7)}
\section{La spirale des nombres premiers}
\subsection{On \'ecrit les nombres premiers en rouge et les autres en noir}
On veut \'ecrire dans la spirale, les nombres premiers en rouge et les nombres 
non premiers en noir. Pour cela on va modifier les proc\'edures 
{\tt ecrisdans, carrentier} en {\tt ecrisprem, carreprem} :
\begin{giaconload}
fonction carreprem(k,n=25,b=8)
  ecrisprem(k,n,b);
  isopoly(4,n);
  saute n;
ffonction:;
fonction ecrisprem(k,n=25,b=8)
  pas_de_cote n/2;
  saute n/2;
  si est_premier(k) alors 
    crayon 1;
  sinon
    crayon 0;
  fsi;
  ecris(k,b);
  saute -n/2;
  pas_de_cote -n/2;
ffonction:;
fonction spireprem(p,k,n=25,b=8)
  local j;
  pour j de 0 jusque p-1 faire
    ecrisprem(j+k,n,b);
    avance n;
  fpour;
  tgav(n);
  pour j de p jusque 2p-1 faire
    ecrisprem(j+k,n,b);
    avance n;
  fpour;
  tgav(n);
ffonction:;
fonction spiraleprem(k0,K,n=25,b=8)
  local j,k,p;
  k:=k0;
  carreprem(k,n,b);
  p:=1;
  k:=k+1;
  tantque k<=K faire
    spireprem(p,k,n,b)
    k:=k+2*p; 
    p:=p+1;
  ftantque;
  avance 0;
ffonction:;
\end{giaconload}
{\bf Remarque} On termine la proc\'edure {\tt spiraleprem} par {\tt avance 0;} 
pour que la derni\`ere instruction \'evalu\'ee soit une instruction tortue.\\

\giacinput{efface;saute 40;spiraleprem(1,73,25,10)}\\
\giacinput{efface;spiraleprem(41,113,25,7)}\\
\subsection{On rep\`ere seulement les nombres premiers \`a l'aide d'un carr\'e rouge}
Dans la spirale, on veut rep\'erer seulement les nombres premiers \`a l'aide 
d'un carr\'e rempli de rouge. Pour cela on va modifier les proc\'edures :\\
{\tt ecrisprem, carreprem} en {\tt premcarre}.\\
On rep\`ere par un disque noir le d\'ebut de la spirale en $k_0$.
\begin{giaconload}
fonction premcarre(k,n=15)
  si est_premier(k) alors 
    rectangle_plein(n,n);
  fsi;
  saute n;
ffonction:;
fonction spirepremcarre(p,k,n=15)
  local j;
  pour j de 0 jusque p-1 faire
    premcarre(j+k,n);
  fpour;
  tgsa(n);
  pour j de p jusque 2p-1 faire
    premcarre(j+k,n);
  fpour;
  tgsa(n);
ffonction:;
fonction spiralepremcarre(k0,K,n)
  local k,p;
  k:=k0;
  crayon 1;
  premcarre(k,n);
  saute -n/2;
  crayon 0;
  disque 2;
  saute n/2;
  p:=1;
  k:=k+1;
  crayon 1;
  tantque k<=K faire
    spirepremcarre(p,k,n);
    k:=k+2*p;
    p:=p+1;
  ftantque;
  avance 0;
ffonction:;
\end{giaconload}
\giacinputbig{efface;saute 50;pas_de_cote 25;spiralepremcarre(1,1001,7)}\\
\giacinputbig{efface;saute 50;pas_de_cote 25;spiralepremcarre(41,1041,7)}\\

\section{La spirale des nombres premiers jumeaux}
On veut rep\'erer dans la spirale que les nombres premiers jumeaux \`a l'aide 
d'un carr\'e bleu et les nombres premiers non jumeaux \`a l'aide 
d'un carr\'e rouge. Pour cela on va modifier les proc\'edures 
{\tt ecrisprem, carreprem} en {\tt carrepremjum}
\begin{giaconload}
fonction tgsa(n)
  tourne_gauche;
  saute n;
ffonction:;
fonction carrepremjum(k,n=15)
  si est_premier(k)  alors 
    si est_premier(k+2) alors 
      crayon 4; rectangle_plein(n,n);     
    sinon
      si (0+crayon)==4 alors 
         rectangle_plein(n,n);crayon 1;
      sinon  
         crayon 1;rectangle_plein(n,n);
      fsi;
    fsi;
  fsi;
  saute n;
ffonction:;
fonction spirepremjum(p,k,n=15)
  local j;
  pour j de 0 jusque p-1 faire
    carrepremjum(j+k,n);
  fpour;
  tgsa(n);
  pour j de p jusque 2p-1 faire
    carrepremjum(j+k,n);
  fpour;
  tgsa(n);
ffonction:;
fonction spiralepremjum(k0,K,n=15)
  local k,p,c;
  k:=k0;
  carrepremjum(k,n);
  c:=0+crayon;
  saute -n/2;
  crayon 0;disque 2;
  saute n/2;
  crayon c;
  p:=1;
  k:=k+1;
  tantque k<=K faire
    spirepremjum(p,k,n);
    k:=k+2*p;
    p:=p+1;
  ftantque;
  avance 0;
ffonction:;
\end{giaconload}
\giacinputbig{efface;pas_de_cote 10;spiralepremjum(1,100,20)}\\
\giacinputbig{efface;spiralepremjum(41,1013,5)}


\section{La spirale, les nombres premiers, la tortue et la r\'ecursivit\'e}
\subsection{Les nombres premiers jumeaux avec une r\'ecursivit\'e terminale}
On peut d\'ecomposer la spirale d\'ebutant par {\tt k0+1} et se 
terminant par la spire contenant {\tt K} en :
\begin{enumerate}
\item le d\'epart : {\tt departspirale(k0,n=15)},
\item la spirale par une spire de longueur $2p$ d\'ebutant par {\tt k0+1} et se 
terminant par la spire contenant {\tt K} : {\tt spiralepremjumr(p,k0,K,n=15)}.\\
Cette spirale est form\'ee par :
\begin{itemize}
\item la premi\`ere spire {\tt spirepremjum(p,k0+1,n)},
\item la fin de la spirale {\tt spiralepremjumr(p+1,k0+2*p,K,n)}.
\end{itemize}
\end{enumerate}
On \'ecrit les proc\'edures pour avoir les nombres premiers jumeaux et non jumeaux  :
{\tt departspirale(k0,n=15)} traite le nombre $k0$ en mettant un petit disque 
noir pour pouvoir rep\'erer le point de d\'epart.\\
{\tt spirepremjum(p,k0+1,n)} a \'et\'e d\'ej\`a programm\'e
{\tt spiralepremjumr(p+1,k0,K,n=15)} est la proc\'edure r\'ecursive qui se termine lorsque $k0\geq K$ on \'ecrit alors la derni\`ere valeur trait\'ee. 
\begin{giaconload}
fonction departspirale(k0,n=15)
  carrepremjum(k0,n);
  c:=0+crayon;
  saute -n/2;
  crayon 0;disque 2;
  saute n/2;
  crayon c;
ffonction:;
fonction spirepremjum(p,k,n=15)
  local j;
  pour j de 0 jusque p-1 faire
    carrepremjum(j+k,n);
  fpour;
  tgsa(n);
  pour j de p jusque 2p-1 faire
    carrepremjum(j+k,n);
  fpour;
  tgsa(n);
ffonction:;
fonction spiralepremjumr(p,k0,K,n=15)
  si k0<K alors
    spirepremjum(p,k0+1,n);
    spiralepremjumr(p+1,k0+2*p,K,n);
  sinon
    saute -n;
    ecris k0;
  fsi;
  avance 0;
ffonction:;
fonction spiralepremj(k0,K,n=15)
  local p;
  departspirale(k0,n);
  spiralepremjumr(1,k0,K,n);
ffonction:;
\end{giaconload}
\giacinputbig{efface;saute 20;departspirale(1,20);spiralepremjumr(1,1,111,20)}\\
\giacinputbig{efface;spiralepremj(47,1111,5)}\\
\subsection{Les nombres premiers avec une r\'ecursivit\'e non terminale}
{\bf Rappel}\\
La $p$i\`eme spire ($p>0$) d'une spirale d\'ebutant par {\tt k0}, commence \`a 
{\tt k0+p*(p-1)+1} et se termine par {\tt p*(p+1)+k0}.
Si {\tt K} est un nombre contenu dans une spire cette spire est de longueur 
{\tt 2*p} avec {\tt p:=ceil((-1+sqrt(1+4*(K-k0)))/2)} car 
{\tt k0+p*(p-1)<K<=k0+p*(p+1)}.\\
On \'ecrit les proc\'edures pour avoir les nombres premiers avec un carr\'e 
rouge. La proc\'edure {\tt spiralepremrec(k0,K,n)} est r\'ecursive et d\'efinit 
la spirale d\'ebutant par {\tt  k0} et se terminant par la spire contenant 
{\tt K} : cette spirale a donc {\tt p:=ceil((-1+sqrt(1+4*(K-k0)))/2)} spires.\\
On d\'ecompose cette spirale {\tt spiralepremrec(k0,K,n)} en
\begin{enumerate}
\item le d\'ebut de la spirale qui a {\tt p-1} spires donc qui se termine par 
le nombre {\tt K=p*(p-1)+k0} : {\tt spiralepremrec(k0,p*(p-1)+k0,n)}
\item la derni\`ere spire qui est la {\tt p}i\`eme spire qui commence par 
{\tt p*(p-1)+k0+1} : {\tt spirepremcarre(p,p*(p-1)+k0+1,n)} 
\end{enumerate}
On utilise les proc\'edures pr\'ec\'edentes qu'on rappelle ici.
\begin{giaconload}
fonction tgsa(n)
  tourne_gauche;
  saute n;
ffonction:;
fonction premcarre(k,n=15)
  si est_premier(k) alors 
    rectangle_plein(n,n);
  fsi;
  saute n;
ffonction:;
fonction spirepremcarre(p,k,n=15)
  local j;
  pour j de 0 jusque p-1 faire
    premcarre(j+k,n);
  fpour;
  tgsa(n);
  pour j de p jusque 2p-1 faire
    premcarre(j+k,n);
  fpour;
  tgsa(n);
ffonction:;
fonction spiralepremrec(k0,K,n=15)
  local p;
  p:=ceil((-1+sqrt(1+4*(K-k0)))/2);
  si p<=0 alors
    si est_premier(k0) alors 
      crayon 1 ;
      rectangle_plein(n,n);    
    fsi;
    saute n/2;crayon 0;disque(2);crayon 1 ;
    saute n/2;
  sinon
    spiralepremrec(k0,p*(p-1)+k0,n);
    spirepremcarre(p,p*(p-1)+k0+1,n);
  fsi;
ffonction:;
\end{giaconload}
\giacinput{efface;pas_de_cote 20;saute 20;spiralepremrec(1,2000,5)}\\
\giacinput{efface;pas_de_cote 20;saute 20;spiralepremrec(41,2000,5)}\\

\section{Exercice :les nombres premiers jumeaux avec une r\'ecursivit\'e non 
terminale}
\'Ecrire une proc\'edure r\'ecursive non terminale pour avoir les nombres 
premiers jumeaux et non jumeaux en s'aidant de ce qui pr\'ec\`ede.
\begin{giaconload}
fonction tgsa(n)
  tourne_gauche;
  saute n;
ffonction:;
fonction carrepremjum(k,n=15)
  si est_premier(k)  alors 
    si est_premier(k+2) alors 
      crayon 4; rectangle_plein(n,n);     
    sinon
       si (0+crayon)==4 alors 
         rectangle_plein(n,n);crayon 1;
       sinon  
         crayon 1;rectangle_plein(n,n);
       fsi;
    fsi;
  fsi;
  saute n;
ffonction:;
fonction spirepremjum(p,k,n=15)
  local j;
  pour j de 0 jusque p-1 faire
    carrepremjum(j+k,n);
  fpour;
  tgsa(n);
  pour j de p jusque 2p-1 faire
    carrepremjum(j+k,n);
  fpour;
  tgsa(n);
ffonction:;
fonction spiralepremjrec(k0,K,n=15)
  local p,c;
  p:=ceil((-1+sqrt(1+4*(K-k0)))/2);
  si p<=0 alors
    carrepremjum(k0,n);
    c:=0+crayon;
    saute -n/2;crayon 0;disque(2);
    saute n/2;crayon c;
  sinon
    spiralepremjrec(k0,p*(p-1)+k0,n);
    spirepremjum(p,p*(p-1)+k0+1,n);
  fsi;
ffonction:;

\end{giaconload}
\giacinput{efface;pas_de_cote 20;saute 20;spiralepremjrec(1,2000,5)}\\
\giacinput{efface;pas_de_cote 20;saute 20;spiralepremjrec(41,2000,5)}

\section{Les nombres premiers de la forme $6k-1$ et $6k+1$ pour $k\geq 1$}
On cherche les nombres premiers jumeaux et non jumeaux de la forme $6k-1$ et 
$6k+1$ pour $k\geq 1$.\\
On d\'ecide de visualiser $6k-1$ et $6k+1$ par un carr\'e : lorsque la tortue 
 a comme cap 0,le triangle inf\'erieur  gauche repr\'esente $6k-1$ et le 
triangle sup\'erieur droit repr\'esente $6k+1$.\\
Si $6k-1$ et $6k+1$ sont des nombres premiers jumeaux, on d\'ecide  
colorier ces 2 triangles en bleu pour obtenir au final un carr\'e bleu.\\
Si $6k-1$ (resp $6k+1$) est un nombre premier non jumeaux, on d\'ecide 
colorier son triangle en rouge (l'autre triangle restant blanc).\\
On range ensuite ces carr\'es selon une spirale comme pr\'ec\'edemment en 
utilisant les fonctions d\'ej\`a \'ecrites {\tt tgsa, ecrisdans}.\\
La fonction finale {\tt spiraleprem6(k0,P,n=16,b=8)} :
\begin{enumerate}
\item \'ecrit {\tt k0} et dessine le carr\'e correspondant \`a {\tt 6*k0-1} et 
{\tt 6*k0+1} puis,
\item  fait {\tt P} spires de longueur 1*2, 2*2,...2$P$.\\
 {\bf Rappel} pour faire une spire de longueur $2p$ la tortue fait $p$ carr\'es 
c\^ote \`a c\^ote puis tourne \`a gauche, saute et fait \`a nouveau $p$ 
carr\'es c\^ote \`a c\^ote.
\begin{itemize}
\item la premi\`ere spire dessine 2 carr\'es : le carr\'e traitant 
{\tt 6*(k0+1)-1} et {\tt 6*(k0+1)+1} et le carr\'e traitant {\tt 6*(k0+2)-1} et  {\tt 6*(k0+2)+1} puis,
\item fait la deuxi\`eme spire jusqu'\`a la {\tt P}i\`eme spire.
\end{itemize}
\end{enumerate}
Au total, le dessin final trace {\tt 1+1*2+2*2+2*3+...+2*P=1+P(P+1)} carr\'es 
qui correspondent aux valeurs de {\tt k} allant de {\tt k0} jusqu'\`a 
{\tt k0+P*(P+1)}.\\
On traite donc les nombres premiers qui vont de {\tt 6*k0-1} jusqu'\`a 
{\tt 6*(k0+P*(P+1))+1}.
\begin{giaconload}
fonction tgsa(n)
  tourne_gauche;
  saute n;
ffonction:;

fonction ecrisdans(k,n=15,b=14)
  pas_de_cote n/2;
  saute n/2;
  crayon 0;
  ecris(k,b);
  saute -n/2;
  pas_de_cote -n/2;
ffonction:;

fonction carreprem6(k,n=16)
  local c1,c2;
  si est_premier(6*k-1) alors 
     c1:=1; 
  sinon 
     c1:=7;
  fsi;
  si est_premier(6*k+1) alors 
     c2:=1; 
  sinon 
     c2:=7;
  fsi;
  si c1+c2==2 alors 
     crayon 4; 
     rectangle_plein(n,n);
      saute n;
  sinon
     crayon c2; 
     rectangle_plein(n,n);
     crayon c1; 
     triangle_plein(n,n);
     saute n;
  fsi;
ffonction:;

fonction spireprem6(p,k,n=16)
  local j;
  pour j de 1 jusque p faire
     carreprem6(k,n);
     k:=k+1;
  fpour; 
  tgsa(n);
  pour j de 1 jusque p faire
     carreprem6(k,n);
     k:=k+1;
  fpour; 
  tgsa(n);
ffonction:;

fonction spiraleprem6(k0,P,n=16,b=8)
  local p,k;
  carreprem6(k0,n);
  ecrisdans(k0,n,b);
  saute n;
  k:=k0+1;
  pour p de 1 jusque P faire
    spireprem6(p,k,n);
    k:=k+2*p;
  fpour;
  saute -n;
  ecrisdans(k-1,n,b);
ffonction:;
\end{giaconload}
\giacinputbig{efface;spiraleprem6(41,10,16,6)}\\
On a trac\'e $1+2*\sum_{k=1}^{10}k=1+10*11$ carr\'es pour $k$ allant de $41$ \`a
$41+10*11$ pour traiter les nombres allant de $6*41-1$ \`a $6*(41+10*11)+1$.\\
\giacinput{41, 41+2*sum(k,k=1..10),6*41-1,6*(41+10*11)+1}\\
\giacinputbig{efface;pas_de_cote 10;saute 20;spiraleprem6(1001,20,10,6)}\\
On a trac\'e $1+2*\sum_{k=1}^{20}k=1+20*21$ carr\'es pour $k$ allant de $1001$ \`a
$1001+20*21$ pour traiter les nombres allant de  $6*1001-1$ \`a 
$6*(1001+20*21)+1$.\\
\giacinput{1001,1001+20*21, 6*1001-1, 6*(1001+20*21)+1}
\end{giacjshere}
\end{document}
