Misez p'tit Optimisez n°79 : Carré Parfait Interdit !

[Xerxes]

Sorry, but there seems to be a misunderstanding. I've noticed some wrong results in your examples, that made me
curious to find out, if it's possible to have a formula with correct results for any argument. My first attempt
was very similar to yours, but I noticed that the results are not correct in any case. So I tried another way
with success I hope.

Code : Tout sélectionner

Trouver le rang de 1669:
 Affichage               Saisie             Remarques
                         [cl]                    Efface affichage.
  >                      [1][6][6][9][shft][spc] Sasir 1669
  ^_                     [-][1][ENTER]           Demander la réciproque c.à.d. la composé (-1) fois
  1627.=^-1.1669.                                1669 est le 1627-ième entier non carré parfait
                         [shft][spc][ENTER]      Vérifions cette allégation
  1669.=^1.1627.                                 Le 1627-ième entier non carré est donc bien 1669

The correct results are 1629 for f^-1(1669) and 1667 for f^1(1627).

[C.Ret]

Yes, you are right, it's look I have made several mistakes when copying results from paper.

So, I restart computations on my SHARP PC-1211 with this code:

Code : Tout sélectionner

1:" " AREAD N:K=1:INPUT "^";K                                         // Saisie de n et facultativement de k
2:R=INT √N,R=R+(√N>.5+R),E=INT .5K,F=E-R+INT √N+(K>2E),F=N+NK+EF      // Calculs de R,E puis F
3:"=" PRINT F;" =^";K;N:END                                           // Affichage peut être affiné

And I obtain the following results:

Code : Tout sélectionner

Keystrokes                Display          Interpretation
1669[DEF][spc]-1[ENTER]   1629.=^-1.1669.  1629 = F^-1(1669)  
[DEF][spc][ENTER]         1669.=^1.1629.   1669 = F(1629)  

I then cross check on my HP-41C

Code : Tout sélectionner

Keystrokes                Display          Interpretation
1669[ENTER^]1[CHS][R/S]   1629             1629 = invF (1669)
1[R/S]                    1669             1669 = F(1629)

And results from other iterative algorithms give the same results.


In conclusion, I don’t know where I made a mistake when coping the previous example of this application.
But you are right; the numeric I published is erroneous.
Thanks for your attention.

The correct example may have been - I put a remark in my previous post.

Code : Tout sélectionner

 Affichage               Saisie             Remarques
                         [cl]                    Efface affichage.
  >                      [1][6][6][9][shft][spc] Sasir 1669
  ^_                     [-][1][ENTER]           Demander la réciproque c.à.d. la composé (-1) fois
  1629.=^-1.1669.                                1669 est le 1629-ième entier non carré parfait
                         [shft][spc][ENTER]      Vérifions cette allégation
  1669.=^1.1629.                                 Le 1629-ième entier non carré est donc bien 1669

I am currently dissecting your code, I try to found how your computation is link to mine.
As I deduce my computation from the observation of several values (and perhaps a few erroneous one ) and I made no true mathematic demonstration of the formulae; I have no prove I am correct.

[Xerxes]

So, I restart computations on my SHARP PC-1211 with this code:

Code : Tout sélectionner

1:" " AREAD N:K=1:INPUT "^";K                                         // Saisie de n et facultativement de k
2:R=INT √N,R=R+(√N>.5+R),E=INT .5K,F=E-R+INT √N+(K>2E),F=N+NK+EF      // Calculs de R,E puis F
3:"=" PRINT F;" =^";K;N:END                                           // Affichage peut être affiné

I've transferred your PC-1211 code to the PB-2000C for verifying. But I need your confirmation
with the results, because something seems wrong with it. I get the same results with your examples,
but some tests with other arguments doesn't work correctly. Can you please check the following
arguments with the PC-1211:

f^99(9)= 2756 instead of 2707

f^20(1225)= 2025 instead of 2015

f^5(1)= 12 instead of 10

I will explain the mathematics of n=n+round((k^2+2dk+2k)/4) later.

[C.Ret]

I just have test all the 3 examples and get, as suspected, the 3 false results :

Code : Tout sélectionner

99[def][spc]9[ENTER]  display 2756.=^9.99.   
1225[def][spc]20[ENTER] display 2756.=^20.1225
5[def][spc]1[enter] display 12.=^1.5.

Looks like my short code was false !

So I start over re-investigeting my notes.
I found my error, I mixt two versions of preliminary code and computations in which the register i didn't stand forthe same thing!

So, i correct my code to this One-Liner version :

Code : Tout sélectionner

1:"F" INPUT N,K : R=INT (.5+√N , E=INT .5K , F=E-(RR>=N)+(K>2E : PRINT N+KR+EF;"^=";K;N:END

[Xerxes]

So, i correct my code to this One-Liner version :

Code : Tout sélectionner

1:"F" INPUT N,K : R=INT (.5+√N , E=INT .5K , F=E-(RR>=N)+(K>2E : PRINT N+KR+EF;"^=";K;N:END

Dear C.Ret, I'm really sorry, but apparently there is still a bug in your formula, if I made no mistake while porting it.
Please check f^-123(12345)=2536, what should be 2474.

[Xerxes]

A closer look at the sequence of the distances between the numbers of the f^k(n)
sequence shows, that it's in general the summation sequence of round(k/2) with an
offset. So we need the difference of the total sum minus the sum below the offset,
to get the distance to the offset.

f^20(1) = 111

1 + 1
2 + 1
3 + 2
5 + 2
7 + 3
10 + 3
13 + 4
17 + 4
21 + 5
26 + 5
31 + 6
37 + 6
43 + 7
50 + 7
57 + 8
65 + 8
73 + 9
82 + 9
91 + 10
101 + 10
111

The distance here is round(k/2*(k/2+1)), because the offset is 1.

Now lets try to calculate f^14(13)=111:

First we need the offset below the summation sequence to be able to subtract the superfluous elements:
d=floor(sqrt(n)*2)-1-(frac(sqrt(n))=0) gives 6, so we have to subtract round(6/2*(6/2+1))=12.
"-(frac(sqrt(n))=0)" is neccessary in case of a perfect square argument.

The total sum of the sequence is round((14+6)/2*((14+6)/2+1))=110. So we have 13+110-12=111.

The formula round(((k+d)/2*((k+d)/2+1))-(d/2)*(d/2+1)) can be simplified to round((k^2+2dk+2k)/4).

So we get following code for k>0 and k<0:

input n,k
d=floor(sqrt(n)*2)-1-(frac(sqrt(n))=0)
n=n+round((k^2+2dk+2k)/4)
print n

It's neccessary to check the results for k<0 with f^-k(result) for plausibility.

[C.Ret]

[...]Dear C.Ret, I'm really sorry, but apparently there is still a bug in your formula, if I made no mistake while porting it.
Please check f^-123(12345)=2536, what should be 2474.

You don't have to be sorry, I currently made a lot of mistaken, typo, inversion, and so on...

I just check your example and I get the correct answer with the last code on my SPARP PC-1211

Code : Tout sélectionner

keystrokes     Display                 Comment
[MODE]         >                       Set to the DEF mode
[shft][ F ]    ?                       Input N
12345[ENTER]   ?                       Input k
-123[ENTER]    2474.=^-123.12345.      Correct result displayed

Tracing into the computation:
1:
INPUT N            N = 12345 User entry
     ,K            K = -123  User entry
:
R=INT (.5+√N,      R = 111   Round of √12345 ~ 111.1080555
E=INT .5K,         E = -62   INT return integer immediately less or equal to argument
                             -123/2 is -61.5 so INT returns -62 here
F=E-(RR>=N)+(K>2E  F=-62-0+1 (RR>N) is false (returns 0) while R²=12321 which is < 12345
                             (K>2E) is in fact K MOD 2 = 1 here -123 > -124
                   F=-61
:  
PRINT N+KR+EF;     2474.     = 12345 - 123*111 + 61*62
      "=^";        =^
      K;           -123.
      N            12345.           
:
END

Here is the corresponding code for HP-41C of the same algorithm:

Code : Tout sélectionner

Pc                 T:       Z:       Y:      X:            L:

001    LBL "79MPO                      n       k             
002    FIX 0                                                 
003    RCL X                  n         k      k             
004    RCl Z         n          k       k      n             
005    SQRT          n          k       k      √n            n
006    RND           n          k       k      R             √n
007    ST* Y         n          k       k.R    R             
008    X^2           n          k       k.R    R²            R
009    R^              k        k.R     R²    n              
010    ST+ Z           k      n+k.R     R²    n              
011    x>y?            k      n+k.R     R²    n              
012    CLx             k      n+k.R     R²      0            vn
013    x<>y            k      n+k.R      0     R²            
014    /               k        k      n+k.R    i.iiii       
015    INT             k        k      n+k.R    i            i.iiii
016    CHS             k        k      n+k.R   -i            i
017    R^              k      n+k.R    -i       k            
018    2             n+k.R    -i        k         2          
019    /                      n+k.R    -i       k/2          2
020    RCL X         n+k.R    -i        k/2     k/2          
021    INT           n+k.R    -i        k/2      e           k/2
022    x>y?          n+k.R    -i        k/2      e           
023    DSE X         n+k.R    -i        k/2      E           
024    NOP           n+k.R    -i        k/2      E           
025    ST* Z         n+k.R    -i.E      k/2      E           
026    x#y?          n+k.R    -i.E      k/2      E           
027    ST+ Z         n+k.R     E-iE     k/2      E           
028    x<>y          n+k.R    mE-iE        E    k/2          
029    RDN                    n+k.R   mE-iE          E       
030    x^2                    n+k.R   mE-iE          E²      E
031    +                              n+k.R    mE-iE+E²      E²
032    +                                      n+k.R+EF       E.(E-i+m)
033    END                                     f^k(n)        

Or printed in short:

Code : Tout sélectionner

01 LBL "79MPO
02   FIX 0  RCL X  RCl Z  SQRT  RND  ST* Y  X^2  R^  ST+ Z  x>y?  CLx
13   x<>y  /  INT  CHS  R^  2  /  RCL X  INT  x>y?  DSE X  NOP
25   ST* Z  x#y?  ST+ Z
28   x<>y  RDN  x^2  +  +
33 END

Le NOP de l'instruction 024 indique une instruction quelconque qui n'a pas d'effet sur la pile et le déroulement du programme (par exemple LBL 00).
C'est dû au DSE précèdent qui dans certains cas va "sauter" le ST* Z très important pour annuler le produit E*F
Le DSE est nécessaire car, contrairement au SHARP PC1211, l'instruction INT sur HP-41 renvoi le mauvais entier en cas d'argument négatif (i.e. -61 pour -61.5 ). Les autres tests permettent de calculer i et m
L'usage de la pile est alambiqué afin de ne pas utiliser d'autre registre mémoire que l pile et de drapeaux.


L'explication de la formule f^k(n) = n + k.R + E.F provient de l'observation des valeurs successives de f^k(n) pour n et k:

f^k(n) en fonction de n et k:

Code : Tout sélectionner

n\k  1:   2:   3:   4:   5:   6:   7:   8:   9:  10:  11:  12:  13:  14:  15:  16:
1 :   2    3    5    7   10   13   17   21   26   31   37   43   50   57   65   73
2 :   3    5    7   10   13   17   21   26   31   37   43   50   57   65   73   82
3 :   5    7   10   13   17   21   26   31   37   43   50   57   65   73   82   91
4 :   6    8   11   14   18   22   27   32   38   44   51   58   66   74   83   92
5 :   7   10   13   17   21   26   31   37   43   50   57   65   73   82   91  101
6 :   8   11   14   18   22   27   32   38   44   51   58   66   74   83   92  102
7 :  10   13   17   21   26   31   37   43   50   57   65   73   82   91  101  111
8 :  11   14   18   22   27   32   38   44   51   58   66   74   83   92  102  112
9 :  12   15   19   23   28   33   39   45   52   59   67   75   84   93  103  113
10:  13   17   21   26   31   37   43   50   57   65   73   82   91  101  111  122
11:  14   18   22   27   32   38   44   51   58   66   74   83   92  102  112  123
12:  15   19   23   28   33   39   45   52   59   67   75   84   93  103  113  124

Les choses sont fort régulières, et comme l'explique Xerxes, il y a un décalage (offset) systématique qui dépend :
de la parité de k (pris en compte par m) et du changement de l'arrondi de √n (pris en compte par i.

Les offsets observés proviennent tous du même fait, le carré n² est distant du carré précédant (n-1)² d'exactement (2n-1) valeurs entières.

Code : Tout sélectionner

 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  26  27  28  29  30  31  32  33  34  35
36  37  38  39  40  41  42  43  44  45  46  47  48
49  50  51  52  53  54  55  56  57  58  59  60  61  62  63
64 ...

[Xerxes]

I just check your example and I get the correct answer with the last code on my SPARP PC-1211

Yes, your latest code is correct. I've overlooked a small bug in the ported code.
Merci for this nice MPO.