getallen puzzel

Speciale getallen zoeken

download programma

download Delphi-7 project

In dit artikel beschrijf ik een Delphi programma dat zoekt naar getallen met een speciale eigenschap.
Het probleem kreeg ik van Luc Denert, die het antwoord had gevonden met porlood en papier .
Dit is zijn probleem:

zoek een getal dat 11x zo klein wordt door het meest linkse cijfer weg te halen en achter het getal te plaatsen. Ik heb het probleem wat algemener aangepakt:

- het linker cijfer van het getal is instelbaar (1..9)
- de deelfactor is instelbaar (2..11)

zoek nu het getal dat factor x zo klein wordt door het eerste cijfer naar achter het getal te verplaatsen.
Voor de volgende beschrijving ga ik uit van het cijfer 2 en ook een factor 2.
Nu is vermenigvuldigen simpeler dan delen zodat ik het probleem heb omgedraaid:

Een getal eindigt op een 2.
Het getal wordt 2x zo groot als deze 2 wordt verplaatst naar links voor het getal.

Het grappige van deze puzzel is dat alleen lagere school rekenkunde is vereist
maar dat zelfs wiskunde leraren moeite hebben met de oplossing.
Na wat vergeefse pogingen zal menigeen zich ook afvragen of zo'n getal wel bestaat.

Het algoritme.

Opmerking: een carry (1 onthouden) schrijf ik als (..)

begin	2
2 x 2 = 4	42
2 x 4 = 8	842
2 x 8 = 16	(1)6842
2 x 6 = 12 + 1 = 13	(1)36842
2 x 3 = 6 + 1 = 7	736842
uiteindelijk	105……...736842
2 x 1 = 2	2105……..736842

Nu zijn het eerste en het laatste cijfer gelijk (en er is geen carry).
Haal de laatste 2 weg en ziedaar een getal dat aan de eis voldoet.
Hieronder een iets aanschouwelijker plaatje:

Het programma

Hierboven zien we het programma aan het werk.
UpDown controls, associated met statictext components, selecteren het eerste cijfer en de vermenigvuldig factor.
De GO button start het zoeken.
Met de SAVE button kopiëren we het resultaat naar het klembord,
zodat het bij een tekstverwerker kan worden ingevoegd.
Is step mode aangevinkt dan stopt het programma na elke stap om het tussenresultaat te tonen.
Carries (onthouden cijfers, veelvouden van 10) worden in rood afgebeeld.

Het getal staat in array A[0…120].
Integer N is de index van array A[ ].
Initialisatie:
N := 0;
A[0] := start cijfer.

Stap 1:
A[N] wordt vermenigvuldigd met 2, het product gaat naar A[N+1] (laagste cijfer) en A[N+2] (carry).
Stap 2:
N := N + 1;
Stappen 1 and 2 worden herhaald tot N = 120 (geen oplossing) of A[N] = A[0] en A[N+1] = 0 (geen carry).
Deze code doet het werk:

Const maxN = 120;  //maximaal aantal cijfers
…..
procedure TForm1.GObtnClick(Sender: TObject);
var carry,i,f,h,N : byte;
    hit : boolean;
begin
 activecontrol := nil;
 for i := 0 to maxN do A[i] := 0;
 displayA(0);
 A[0] := N0upDown.Position;  //starting digit
 f := factorUpdown.Position; //factor
//--
 N := 0;  //array A index
 repeat
  inc(N);
  A[N] := A[N-1]*f + A[N];
  h := 0;
  while A[N+h] >= 10  do   //handle carries
   begin
    carry := A[N+h] div 10;
    A[N+h] := A[N+h] mod 10;
    inc(h);
    A[N+h] := A[n+h] + carry;
   end;
  hit := (A[N] = A[0]) and (h=0);
until (N = maxN) or  hit;
//--
 if hit then begin
              msgText.Caption := 'solution';
              displayA(N);
             end
  else begin
        msgText.Caption := 'no solution';
        label4.Caption := '';
       end;
end;

Step mode

Als stepMode is aangevinkt dan worden tussenresultaten getoond.
Mechanisme: na elke stap wordt variable stopFlag true gezet.

while stopFlag do application.ProcessMessages;

Indrukken van space bar reset de stopflag zodat het proces verder kan.
Hiervoor is wel nodig dat de keyPreview property "true" staat in de form1 object inspector.
De zoekoperatie begint met
Activecontrol := nil.
Dit verhindert dat het character naar de GO button gaat want die heeft de focus na het aanklikken.

Display van array A[ ]

Ik gebruik daar voor een paintbox omdat dan de cijfers in verschillende kleuren afgedrukt kunnen worden.
Het Courier new font heeft characters van gelijke breedte.
A[1] staat rechts, de character positie x wordt steeds verlaagd om het volgende cijfer te positioneren.
procedure displayA(n : byte); doet het werk.
n is het aantal cijfers.
Een cijfer (ongelijk 0) met hogere positie dan n wordt in rood afgebeeld.

Het klembord

Clipbrd unit is aan de uses clausule toegevoegd.
Als string s het resultaat bevat dan gaat s zo naar het klembord:

clipboard.AsText := s;

Maar eerst moet A[ ] naar s gekopieerd worden, hoogste cijfer eerst:

var s : string;
   i,n,p : byte;
begin
 s := '';
 n := maxN;
 while (A[n] = 0) and (n > 0) do dec(n);//find first non zero digit
 p := 0;
 for  i := n downto 1 do 
  begin
   if p = 3 then begin
                  s := s  + '.';
                  p := 0;
				 end; 
   s := s + char(A[i] + ord('0'));
   inc(p);
  end; 
end;

Zoals hierboven vermeld loste Luc Denert het probleem voor een factor 11
en begincijfer 1 handmatig op.
Hij maakte mij ook nog attent op een vreemde eigenschap van het antwoord:
Splits het getal in tweeën.
Onder elkaar gezet en opgeteld is het antwoord 999...99999.

Voor meer details verwijs ik naar de source code.