Une etude avec le logiciel Maple

Un palindrome :                    tu l'as trop écrasé césar ce port-salut

Un Annagramme strict :       mizony,   ynozim

recherche des nombres "palindromes"  a qui verifient
9a et a sont annagrammes stricts en base 10.

Exemple de programme "brutal"

pa:=proc(n)
local i,j,L,m;
for i to n do
L:=convert(i,base,10);
j:=add(L[nops(L)-m+1]*10^(m-1),m=1..nops(L));
if 9*i=j then print(`un palindrome`,i,9*i) fi
od;
end;

pa(20000);# c'est long pour trouver les deux premiers 1089 et 10989

Utilisant une premiere remarque :le nombre a cherch'e ne peut se
terminer que par un 9, un programme 10 fois plus rapide :

paplus:=proc(n)
local i,j,L,m;
for i from 9 by 10 to n do
L:=convert(i,base,10);
j:=add(L[nops(L)-m+1]*10^(m-1),m=1..nops(L));
if 9*i=j then print(`un palindrome`,i,9*i) fi
od;
end;

paplus(2000); ce n'est guere satisfaisant!

Alors un peu de maths:

lemme 1: 9*a etant divisible par 9 et a ayant les memes chiffres que
 9*a, a est divisible par 9
lemme 2: a est de la forme 10...89.

d'ou un algotithme plus rapide :
Pa:=proc(n)
local i,ii,j,L,m;
for i from 0 by 9 to n do
ii:=100*i+89+10^(length(i)+3);
L:=convert(ii,base,10);
j:=add(L[nops(L)-m+1]*10^(m-1),m=1..nops(L));
if 9*ii=j then print(`un palindrome`,ii,9*ii) fi
od;
end:
En voici le resultat :

Pa(10000);
                             un palindrome, 1089, 9801
                            un palindrome, 10989, 98901
                           un palindrome, 109989, 989901
                          un palindrome, 1099989, 9899901
                         un palindrome, 10891089, 98019801
                         un palindrome, 10999989, 98999901
Allons plus loin :
lemme 3: soit a une solution, b un mot de chiffres, alors c=aba,
obtenu par concatenation est une solution, si b*, obtenu a partir de
b en supprimant un nombre maximum et egal de zeros a ses extremites, est
une solution ou le mot vide.

 Definition : nous appellerons solution irreductible, toute solution
n'admettant pas de sous-mot solution.
par exemple 10891089, 108901098901089  sont des solutions qui ne sont
pas irreductibles.

 Problemes:
1- comment demontrer simplement que toutes les solutions irreductibles
sont de la forme a=10999...989. (je connais une preuve, mais elle est fastidieuse).
2- comment demontrer que toute solution est divisible par 11; (si une
solution a un nombre pair de chiffres, alors elle est divisible par
11, car 5*a=(9*a+a)/2 est un mot palindrome ayant un nombre pair de
chiffres).    C'est joli !

Une etude de factorisation nous montre que ces nombres sont
divisibles par 9*11=99 et que le quotient de a par 99 est un nombre
form'e que de 1, sil est irreductible.

D'ou,

 Une generation des nombres palindromiques irreductibles.

a:=proc(n)
local i,L;
L:=[9,8,seq(9,i=1..n-2),0,1];
sum(L[j]*10^(j-1),j=1..2+n);
end:
seq([a(n),9*a(n)],n=2..6);
seq(a(n)/99,n=2..6);

On introduit alors les polynomes 1+X+X^2+...+X^n.
Pa:=proc(n)
local i;
global Q;
Q:=sum(X^i,i=0..n-1);
99*subs(X=10,Q)
end:

(L'idee d'introduire ces polynomes n'a pas ete immediate pour moi)

verification:
seq([a(n),Pa(n)],n=2..6);

Or on obtient 9 comme 10-1 et 99 comme 10^2-1.
Ceci m'a suggere le recours aux polynomes dits cyclotomiques
dont voici une definition :
Definition 2: Le nieme polynome cyclotomique est le produit des
monomes X-alpha, avec alpha parcourant les racines primitives nieme de l'unite.
( i.e. alpha est zero de X^n-1, sans etre zero de X^k-1, pour k<n).

Un pstit programme avec "Maple" :

with(numtheory,cyclotomic);  (appel a une bibliotheque de calcul)
cyclotomic(3,X);cyclotomic(105,X);
seq([cyclotomic(k,X),Pa(k),Q,factor(Q)],k=2..6);

Il semble donc que :
cyclotomic(k,X) divise le polynome Q de Pa(k); et donc
subs(X=10,cyclotomic(k,X)) divise a(k)

Une autre definition: on appelle nombre cyclotomique
la valeur d'un polynome cyclotomique en un entier k.

Ainsi nos nombres palindromes irreductibles sont lies a des nombres 
cyclotomiques.

Vers une presentation abstraite, en utilisant sum(X^i,i=0..n-1)=(X^n-1)/(X-1)

P:=proc(n) (X+1)* (X^n-1) end:
A:=[P(n),(X-1)*P(n),factor(P(n)/cyclotomic(n,X)/(X^2-1))];
seq(subs({X=10},A),n=2..6);

nous avons une generation abstraite de nos nombres palindromes
eval(subs({n=105,X=10},A));

nous avons vu que le nombre cyclotomique subs(X=10,cyclotomic(n,X))
divise notre nombre palindrome a(n); on a beaucoup mieux, comme
consequence de la definition des polynomes cyclotomiques :
     Soit pour n donne, l'ensemble des diviseurs de n, notons le div(n);
alors le produit des nombres subs(X=10,cyclotomic(d,X)) avec d dans
div(n) divise a(n) et le quotient est 11.

exemples
a(8)/subs(X=10,cyclotomic(1,X)*cyclotomic(2,X)*cyclotomic(4,X)*cyclotomic(8,X));
a(7)/subs(X=10,cyclotomic(1,X)*cyclotomic(7,X));
a(30)/subs(X=10,cyclotomic(1,X)*cyclotomic(2,X)*cyclotomic(3,X)*cyclotomic(5,X)*cyclotomic(6,X)*cyclotomic(10,X)*cyclotomic(15,X)*cyclotomic(30,X));

On verifie :
with(numtheory,cyclotomic,divisors);
test:=proc(n)
local i,div;
div:=[op(divisors(n))];
a(n)/product(subs(x=10,cyclotomic(div[i],x)),i=1..nops(div));
end;
seq(test(i),i=1..110);
for i from 2  while test(i)=11 and i<200 do od;print(i);

Grace a cette remarque on peut trouver de grands facteurs de a(n)

deca:=proc(n)
local i,div;
div:=[op(divisors(n))];
seq(ifactor(subs(x=10,cyclotomic(div[i],x)),easy),i=1..nops(div));
end;

Exemples
deca(62);ifactor(a(62)/11,easy);

seq({coeffs(cyclotomic(i,X),X)},i=100..105);
on a un polynome cyclotomique dont les coefficients ne sont pas dans {-1,0,1}.
deca(105);ifactor(a(105)/11,easy);

Sur la division par 11 :
      Les solutions irreductibles sont obtenues en faisant X=10 dans le
      polynome X^(n+1)+X^n-X-1.
Ces polynomes admettant X+1 comme facteur, ils
sont divisibles par 11; maintenant employons le lemme 3, toute
solution s'ecrit comme somme de solutions irreductibles multipliees
par des puissances de 10, elle est donc divisible par 11.


RESULTAT: les solutions du probleme sont les nombres a de la forme
99*b, ou b est un nombre forme que de 0 et de 1, symetriques
(palindrome), n'ayant aucun 1 ou 0 isole.


Quels sont parmi les nombres palindromiques ceux qui s'ecrivent comme
 produit de 99 par un nombre premier ?
pour les irreductibles, une premiere etude :

for i from 1 to 70 do
if isprime(eval(subs(X=10,cyclotomic(ithprime(i),X)))) then
print(a(ithprime(i))=ifactor(a(ithprime(i)),easy),`bravo`) fi;
od:

autres exemples:
a:=108901098901089;a:=10989001099999890010989;
evidemment resoudre une telle question reviendrait a trouver une
suite explicite de nombres premiers!
voici un programme qui en donne beaucoup:

essai:=proc(k1,k2,k3)
local i,L,p;
global j;
L:=[seq(1,i=1..k1),seq(0,i=1..k2),seq(1,i=1..2*k3+1),seq(0,i=1..k2),seq(1,i=1..k1)];
p:=nops(L);
j:=add(L[i]*10^(p-i),i=1..p);
if isprime(j) then j else 0 fi;
end:

On obtient un certain nombre de la forme 99*premier par :
for k1 from 2 to 5 do
  for k2 from 2 to 10 do
    for k3 to 20 do
if modp(2*k1+2*k3)+1,3)>0 and gcd(k1,2*k3+1)=1 then
  r:=essai(k1,k2,k3);
  if r>0 then print(r,99*r,[k1,k2,2*k3+1]) fi;
fi;
    od;
  od;
od;

(On a utilise les faits que - pour "k3 pair", il n'y a pas de solution.
                            - et pour 2k1+2k3+1=0 modulo 3 non plus.

Resultats de nombres palindromes composes de la forme "99*premier":


           1100011100011, 108901098901089, 980109890109801

  110000011111110000011, 10890001099999890001089, 98010009899999010009801

  1100000001111111111111111111000000011,
  108900000109999999999999999989000001089,
  980100000989999999999999999901000009801

  11000000001110000000011, 1089000000109890000001089, 9801000000989010000009801

  111000011111110000111, 10989001099999890010989, 98901009899999010098901

  111000001111111111100000111, 10989000109999999998900010989,
			       98901000989999999990100098901

  11100000011111000000111, 1098900001099989000010989, 9890100009899901000098901

  11100000011111111111111111000000111, 1098900001099999999999999989000010989,
				       9890100009899999999999999901000098901

        111100111001111, 10998910989109989, 98990198901989901

  111100000001111111111100000001111, 10998900000109999999998900000109989,
				     98990100000989999999990100000989901

  111110000111000011111, 10999890010989001099989, 98999010098901009899901

  1111100000000011111111100000000011111,
  109998900000001099999998900000001099989,
  989990100000009899999990100000009899901

On peut revoir ces resultats a partir des polynomes
cyc:=proc(k1,k2,k3)
local X,P;
P:=(X^k1-1)/(X-1)*(X^(k1+2*k2+k3)+1)+(X^k3-1)/(X-1)*X^(k1+k2);
factor(P),99*subs(X=10,P);
end:

On remarque que si d est le pgcd de k1 et k3, X^d-1 divise P;
on remarque aussi que 2k1+2k3+1>0 modulo 3  generalise le fait que le
PGCD de k1 et de 2*k3+1 soit 1   (gcd(k1,2*k3+1)=1). 

Ce recours "abstrait" permet d'ameliorer l'algorithme precedent :

for k1 from 2 to 10 do
  for k3 to 10 do
u:=2*k1+2*k3+1;
if isprime(u) then
    for k2 from 2 to 10 do
  if  modp(k2,u)>0 and  modp(k2+k1+2*k3+1,u)>0
  then
  r:=essai(k1,k2,k3);
    if r>0 then print(r,[k1,k2,2*k3+1]) fi;
  fi;
    od;
fi;
  od;
od;

Etc ...

		                 Esope reste ici et se repose