[VA] SRC #008 - 2021 is here !

[Valentin Albillo]

      
Hi all:

First of all, thanks to all of you for the warm welcome to my SRC #008 and the many contributions by Nihotte(lma), Vincent Weber, J-F Garnier, robve, Dwight Sturrock, Albert Chan, StephenG1CMZ, Albert Chan (again), Gene, ijabbott, telemachos, Maximilian Hohmann, Gerson W. Barbosa and last but not least, Albert Chan, thanks a lot to all of you for your interest and your solutions and quite varied approaches

These are my original solutions:
        
1) Let's partition 2021 into a set of positive integer numbers that add up to 2021. Find the set of such numbers whose product is maximum, and output that maximum in all its full glory.


It's easy to see that only using just the terms 2 and 3 will produce the maximum product, because:

• if a term = 5 then we can replace it by 2+3, which contributes the same to the sum, 5, but increases the product as 2*3 = 6 > 5.
  The same is true for terms >5 (e.g.: 6 = 3+3 but 3*3 = 9 > 6, 7 = 3+2+2 but 3*2*2 = 12 >7, etc.)
        
• if a term = 4 then it can be replaced by 2+2, which contributes the same for both the sum and the product.
        
• if a term = 1 then 1+2 can be replaced by 3, as 1*2 = 2 < 3, and 1+3 can be replaced by 2+2, as 1*3 = 3 < 2*2 = 4.

Thus only terms 2 and 3 will need to be considered, and furthermore as three 2's can be replaced by two 3's, which have the same sum (6) but 2*2*2 = 8 < 3*3 = 9, then at most two 2's can be part of the solution. As 2021 = 3 * 673 + 2, then the maximum product will be the product of 673 3's and one 2, i.e: Max. P = 2*3⁶⁷³.

In general, for integer N = 3 * q + r, where q is the quotient and r is the reminder, the maximum products are:

            - if r = 0: Max. P = 3^q (no 2's, all are 3's)
            - if r = 1: Max. P = 2²*3^q-1 (two 2's, the rest are 3's)
            - if r = 2: Max. P = 2*3^q (one 2, the rest are 3's)

For real N all summands must be equal because of the Arithmetic-Geometric Means inequality, and they must be as close to e = 2.718+ as possible, which is the reason behind the need for a majority of 3's in the integer N case, as 3 is the integer closer to e.

Also, as I am so adamant in HP calcs being used to solve the questions I propose, you may wonder where do HP calcs intervene in my solution ? Well, to fulfill the "output that maximum in all its full glory" part of the task, that's where, and to that effect I've concocted this 5-line (220-byte) program for the HP-71B, which exactly computes the 322 digits of the max. product P = 2*3⁶⁷³ in half a second using the excellent J-F Garnier's Emu71 emulator:

      1   DESTROY ALL @ OPTION BASE 0 @ DIM A(36) @ K=10^9 @ A(0)=2*3^13 @ P=0
      2   FOR J=1 TO 110 @ MAT A=(729)*A @ FOR I=0 TO P @ A(I+1)=A(I+1)+A(I) DIV K
      3   A(I)=MOD(A(I),K) @ NEXT I @ P=P+SGN(A(P+1)) @ NEXT J @ J=0
      4   DISP STR$(A(P)); @ FOR I=P-1 TO 0 STEP -1 @ J=J+1 @ IF J=5 THEN DISP @ J=0
      5   A$=STR$(A(I)) @ DISP RPT$("0",9-LEN(A$));A$; @ NEXT I @ DISP

            Line 1      initializes
            Lines 2-3   compute the 322-digit product
            Lines 4-5   output the result

         >RUN

              2532995521886826292328149655127793939711079
            6485699809049268130708906002579675557​88084132
            383052323458136675408253781974882864255212314
            264505911807500659338824573​345556963262198232
            747186628808383273213581619626233679533487706
            06025349498189611​2664520885716630483899029142
            003916544644957076791520721759240671604739781
            810307846


2) Numerically evaluate as accurately as possible this nice definite integral using your favorite HP calc (per standard notation, the | ... | vertical bars mean "absolute value"):



and for extra points, see if you can symbolically recognize the resulting value. You'll need a sufficiently accurate value to do it, though ...


The funny thing about this integral is that its value remains the same if you replace 2.021 by any positive real value !!

This means that the integral's value is the same for 2.021 or 0.2021, 20.21, 2021, Pi, e, the Golden Ratio, your age, your phone number, etc. So it doesn't actually matter whether the "." in 2.021 is taken as the decimal point or as the thousands separator, as one of you wondered   

Let's compute it using Free42 Decimal for extra accuracy. We'll need this short 32-step (60-byte) program which defines a generalized version of the function to integrate (you can specify 2.021 or any other constant):

      LBL "SRC82"      Y^X          1/X             ABS
      MVAR "X"          2           X<>Y            RCL "X"
      MVAR "Z"          /           STO ST T        STOx ST T
      RCL "Z"          X<>Y          x              Y^X
      SIN               2           RCL "Z"          +
      ENTER            RCL "X"      COS             LN
      ABS              1/X          STOx ST T       RCL/ ST Y
      RCL "X"          Y^X           +              END

and now, using the built-in Integrate application (the "S" are Integral symbols):

      [Sf(x)]   -> Select Sf(x) Program
      [SRC82]   -> Set Vars; Select Svar
                   [X][Z]

      2.021 [X] -> X=2.021
            [Z] -> [LLIM][ULIM][ACC]   [S]

       0 [LLIM] -> LLIM=0
    [PI] [ULIM] -> ULIM=3.14159265359
     1E-6 [ACC] -> ACC=0.000001
            [S] -> Integrating -> 2.46739926409
      [+][SHOW] -> 2.46740110027233423194...

All that remains now is to symbolically recognize this value, for example using my IDENTIFY program (listing, description and examples here), and the result is Pi²/4, which evaluates to 2.46740110027233965470... so we've got 15 correct digits. You may vary the 2.021 value above and re-compute the integral, to check that indeed you get the same result.


3) Decompose 4/2021 into a sum of three fractions of the form 1/K where K is a positive integer.


As we saw in (1) above, 2021 is a number of the form N = 3*m + 2 and for such numbers we have the algebraic identity:

      4/(3*m + 2) = 1/(3*m + 2) + 1/(m + 1) + 1 /((m + 1) * (3*m + 2))

so we'll use this trivial program to ask for N (which must be of the form 3*m + 2) and output the resulting denominators:

      1   DESTROY ALL @ INPUT N
      2   IF MOD(N,3)#2 THEN DISP "Not of form 3*m+2" @ END
      3   M=N DIV 3 @ DISP N;M+1;N*(M+1)

            >RUN
            ? 2021
                        2021      674      1362154

so:       4/2021 = 1/2021 + 1/674 + 1/1362154, and of course many other solutions are possible as well.

As another example, using the program for 2027, which is a prime number and thus can't be factorized, we get:

            >RUN
            ? 2027
                        2027      676      1370252

so  4/2027 = 1/2027 + 1/676 + 1/1370252, and so on and so forth.

Note that as the first summand fraction is 1/N, the remaining two add up to 3/N, thus we also have a decomposition of 3/N into two 1/K fractions.

Thanks again for your interest and contributions.

Best regards.
V.

Edited to include a slightly optimized version of the BASIC code (30 bytes shorter)