+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" (/thread-12656.html)
[VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Valentin Albillo - 03-21-2019 02:08 AM
Hi, all ! Happy Spring to all of you !
... and once again to commemorate its arrival, here you are, a brand new Short & Sweet Math Challenge #24 "Spring Special 5-tier" to give you all a chance to put to good use both your favourite HP calculator and your programming ingenuity (*NOT* your Google Search proficiency). Try all 5 tiers below and see what's your top one !
Rules:
- Any HP calc of your choice may be used but I'll suggest a Minimum Recommended Model (MRM) for each tier, which is the simplest model I deem capable of solving it more or less comfortably.
- Using anything other than a physical or emulated HP calculator is strictly disallowed. Also no VBA, Excel. Pascal, C/C#/C++, Java, Python, Haskell, etc. code, please go elsewhere for that. You must write your code in a language supported in some HP calc (i.e.: RPN, RPL, 71B BASIC/FORTH, etc).
- Googling the solutions is lame beyond belief and, frankly, if you do you'll be but a sore loser in my eyes
.
Tier 1: Noob
[MRM: HP-11C and up]
Let's begin with something affordable. As it happens, I have 2 HP-71B and a 41C in my collection and I love them dearly so I'll pay them a little homage here: we'll call Homage Number to any 10-digit positive integers which are multiples of 271, divisible by 41 and further their digits are all distinct.
The Challenge:
Write a program that takes no inputs but simply finds out and outputs just how many Homage Numbers there are. No need to output any of them, just count'em and do it fast !
Your code should be as fast and short as possible, in that order. I'll post my original code (a 2-liner) and results for the HP-71B .
Tier 2: Beginner
[MRM: HP-29C and up]
Consider the function SB(N) which returns the sum of the base-B digits of an integer N. For instance:
S2(2019) = S2(111111000112) = 1+1+1+1+1+1+0+0+0+1+1 = 8
S5(2019) = S5(310345) = 3+1+0+3+4 = 11
S10(2019) = 2+0+1+9 = 12
S16(2019) = S16(7E316) = 7+E (=14) +3 = 24
S36(2019) = S5(1K336) = 1+K (=20) +3 = 24
The Challenge:
Write a program that accepts a base B (2 to 36) and outputs in order those prime numbers N such that SB(N) is composite and distinct from the previous ones.
For instance, this is what your program should generate for bases B = 6, 8 and 16 (hexadecimal):
B = 6: 11, 19, 23, ... 179, ...
B = 8: 11, 13, 23, ... 191, ...
B = 16: 19, 23, 29, ... 223, ...
Once verified that your code reproduces the above sample results, go on and generate the corresponding sequences for base B = 31 first and then for base B = 7 .
What results do you get ? Which is the smallest (first) prime in each sequence ? How many elements can you generate for each sequence ? What about other bases ?
Again, your code should be as fast and short as possible, in that order. I'll post my original code (a 6-liner) and results for the HP-71B .
Tier 3: Intermediate
[MRM: HP-25 and up]
Consider the real numbers 77.4019... and 231.4859... , which are sums of distinct non-negative integer powers of e (= exp(1) = 2.71828...):
77.4019... = e1 + e3 + e4
231.4859... = e0 + e2 + e3 + e4 + e5.
Those positive real numbers that are either powers of e or sums of distinct powers of e form an increasing sequence whose first term is 1 (i.e.: e0) and matter of fact we have that 77.4019.. is the 26th term in the sequence and 231.4859... is the 61th term.
The Challenge:
Generalizing to powers of an arbitrary real number P >= e, write a program or function which accepts as input both P and an index k and returns the corresponding kth term in the sequence (in the example above we would have MyFunction(e, 26) = 77.4019... and MyFunction(e, 61) = 231.4859... ). Your code should be as short and fast as possible.
Now use your program/function to find the 1,000,000th term and the 3,141,593th term when P = e as well as the 1,234,567th term and the 2,718,282th term when P = Pi. Also, just for show, use it to list the first 10 terms or so for each sequence.
I'll post both a 1-line user-defined function for the HP-71B and an equivalent 24-step RPN program for the HP-25 (which should work with little or no change in all RPN-based HP calcs).
Tier 4: Advanced
[MRM: HP-11C and up]
Consider the n-point dataset (xi , yi) where xi = 1, 2, 3, 4, 5, 6, ..., n (the natural numbers) and yi = 2, 3, 5, 7, 11, 13, ..., pn (the prime numbers), and the (n-1)st degree polinomial fit to this dataset of the form:
P(x) = a0 + a1 (x-1) + a2 (x-1) (x-2) + ... + an-1 (x-1) (x-2) (x-3) ... (x-(n-1))
The Challenge:
Write a program that takes no inputs but computes and outputs the limit of the sum of the coefficients a0, a1, ... , an-1 when n tends to infinity. Your program must be as short and fast as possible and must compute the limit to the 10-12 digits maximum accuracy of your calc, give or take a few ulps.
I'll post a 4-line, 168-byte program for the HP-71B which computes and outputs the limit in ~0.2 sec (Emu71) but a fast RPN version for the HP-11C and up is also perfectly possible.
Tier 5: Guru
[MRM: HP-11C and up]
Surely you're well aware of the elementary trigonometric function sin(x), you know, the wavy one. Now consider a related function, which henceforth I'll call cin(x) which has the defining property that cin(cin(cin(x))) = sin(x).
The Challenge:
Write a program or function which accepts an argument x in the range [-Pi, Pi] and outputs the corresponding value of cin(x). The faster and shorter the better but you should strive for maximum accuracy (at least 8-10 correct digits in the whole range, give or take a few ulps).
Once written, use it to tabulate cin(x) for x = 0.0, 0.2, 0.4, ..., 1.0 and also to compute cin(Pi/2), cin(-0.71), cin(2.019), and with the experience gained do likewise with another similar function tin(x) which has the property that tin(tin(x)) = sin(x).
I'll give a short program for the HP-71B which achieves about 10 correct digits for any argument in [-Pi, Pi].
Hint: You can check that you get adequately accurate values of cin(x) by simply computing cin(cin(cin(x))) and comparing the results with sin(x). Likewise with tin(x).
Finally, the usual caveat:
- Please do NOT include CODE panels in your replies to this thread, as it makes it difficult for me to generate the online PDF document which will include the whole thread. I expect you'll kindly comply with this requirement but otherwise I'll remove from the final PDF document any replies featuring CODE panels. Thank you.
I'll post my original solutions in a week or so but meanwhile let's see what you can do.
That's all. Hope you'll enjoy it !
V.
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Albert Chan - 03-21-2019 12:21 PM
Homage number must be divisible by 271 * 41 * 9 = 99999
Since 1e5 mod 99999 = 1, Homage number had another property:
top 5 digits + bottom 5 digits = 99999
Example, since 10234 + 89765 = 99999, smallest Homage number is 10234 89765
Top digit > 0, thus 9 cases to choose.
2nd digit cannot be the first, or 9 - first, thus 10 - 2 = 8 cases ...
Total Homage numbers = 9 * 8 * 6 * 4 * 2 = 3456
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Paul Dale - 03-21-2019 12:30 PM
I'm not sure why but tier 3 and tier 4 look like the easiest.
Spoilers towards the end.
Anyway, a 24 step program for tier 3 for the HP 25:
01 CLREG
02 1
03 x<>y
04 x=0?
05 GTO 24
06 2
07 /
08 INT
09 LASTx
10 FRAC
11 x=0?
12 GTO 17
13 Rv
14 x<>y
15 STO+ 0
16 GTO 19
17 Rv
18 x<>y
19 1
20 e^x
21 *
22 x<>y
23 GTO 04
24 RCL 0
For the Pi flavour, change steps 19 and 20 to: Pi and NOP.
The 1,000,000th term is 278,394,443.2 and the 3,141,593rd term is 1,601,007,657. Both in several seconds on a real 25.
The 1,234,567th term for Pi is 9,091,632,462 and the 2,718,282nd term is 30,446,503,22x (x being beyond the accuracy of the 25). Again, fairly quickly.
The key observation being that:
$$ \sum_{i=0}^n e^i = \frac{e^{n + 1} - 1}{e - 1} < e^{n + 1} $$
which means that the position expressed in binary determines the powers used. Note that 21 + 23 + 24 = 26 and 20 + 22 + 23 + 24 + 25 = 61 and compare to the initial examples.
Larger bases also have this property. I didn't try to prove that e is the smallest base for which this holds true, which is good because the smallest base is, unsurprisingly, two.
Pauli
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - J-F Garnier - 03-22-2019 08:04 AM
(I noticed that the SSMC24 was Valentin's post #314 at the time of writing :-)
Tier 5: Guru
In summary : Write a program or function cin(x) which has the defining property that cin(cin(cin(x))) = sin(x).
Once written, use it to tabulate cin(x) for x = 0.0, 0.2, 0.4, ..., 1.0
From the properties of sin we can restrict the search of cin(x) in the interval [0,pi/2].
The problem implicitly assumes that the cin(x) function is unique, otherwise it would make no sense to discuss the cin(x) values.
If we understand 'function' in the mathematic sense of an analytical, non-pathologic function, this may be true.
But if we understand 'function' in the computer science sense of a procedure that takes one argument and returns one result, there are very likely many cin 'functions' such as cin(cin(cin(x)))=sin(x)
One such solution for the HP71 is below:
10 ! SSMC24A
20 DEF FNC(X)
30 IF X=0 THEN Y=0 @ GOTO 70
40 X=ABS(X)
50 Y=LN(X)
60 IF Y<2 THEN Y=1+EXP(X) ELSE Y=SIN(LN(LN(X-1)-1))
70 FNC=Y
80 END DEF
85 !
90 FOR X=0 TO 1 STEP .1
100 PRINT FNC(FNC(FNC(X)));SIN(X)
110 NEXT X
>RUN
0 0
9.98334166508E-2 9.98334166468E-2
.198669330795 .198669330795
.295520206664 .295520206661
.389418342308 .389418342309
.479425538604 .479425538604
.564642473395 .564642473395
.644217687238 .644217687238
.717356090899 .7173560909
.783326909628 .783326909627
.841470984808 .841470984808
I don't take this solution too seriously :-)
Still searching for a better one...
J-F
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Valentin Albillo - 03-23-2019 12:40 AM
Hi J-F, long time no see !
(03-22-2019 08:04 AM)J-F Garnier Wrote: (I noticed that the SSMC24 was Valentin's post #314 at the time of writing :-)
Yes, that was intentional on my part. Notice also that Paul Dale's post just before yours is his post #1444, i.e. 382, which has the maximum number of 4's (three) in which a square can end.
Quote:The problem implicitly assumes that the cin(x) function is unique, otherwise it would make no sense to discuss the cin(x) values. If we understand 'function' in the mathematic sense of an analytical, non-pathologic function, this may be true.
Yes, that's the kind of "function" I intended.
Quote:But if we understand 'function' in the computer science sense of a procedure that takes one argument and returns one result, there are very likely many cin 'functions' such as cin(cin(cin(x)))=sin(x)
One such solution for the HP71 is below ...
Quite clever of you to find the trick, but certainly that's not what I intended as a solution. The trick will work for any function (not just sin(x) ) and for any number of function compositions (not just 3), but it's of no mathematical value or interest whatsoever.
Also, you overdid it a little, there's no need of EXP's or LN's to make it work, simply adding and later subtracting a suitable constant would do just as well (and faster). Finally, your line
30 IF X=0 THEN Y=0 @ GOTO 70
can be shortened to
30 IF X=0 THEN END
because if a multi-line user-defined function ends without assigning the return value then it simply returns 0 by default. And IF X=0 can be replaced by IF NOT X
Quote:I don't take this solution too seriously :-)
Indeed you shouldn't, neither do I ...
Quote:Still searching for a better one...
Good luck with that, I'm sure you'll succeed and I'm eager to see what you come up with.
Very glad to see you post here, much appreciated. Thanks for your continued interest in my S&SMC's and have a nice weekend.
V.
P.S.: What would it take to lure you into releasing a version of Emu71 which would run on a 32-bit or 64-bit Windows OS, or at least on Android ? Begging ? Bribing ? Taking some relative hostage ? Just plain ol' money ? You tell me, please, it's really affecting my productivity !!
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - J-F Garnier - 03-23-2019 07:53 AM
(03-23-2019 12:40 AM)Valentin Albillo Wrote: Hi J-F, long time no see !I'm still following your various challenges, even participated to the the last one.
...
Very glad to see you post here, much appreciated. Thanks for your continued interest in my S&SMC's and have a nice weekend.
And when I don't participate, it may just mean I have nothing interesting to contribute.
Quote:I investigated a few ideas, without success up to now.Quote:Still searching for a better one...Good luck with that, I'm sure you'll succeed and I'm eager to see what you come up with.
Quote:P.S.: What would it take to lure you into releasing a version of Emu71 which would run on a 32-bit or 64-bit Windows OS, or at least on Android ?It's a bit OT - well maybe not so much since the HP71 and Emu71 are your favourite tools for your challenges.
In short, the answer is that I don't have the competences to port my Emu71/Dos to Windows, MacOS, Linux, not to mention iOS, Android. However, Emu71/DOS is open source...
And you know for sure that there is already an excellent Emu71 running on Windows (32/64 bits), and also an HP71 emulator for Android.
J-F
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Albert Chan - 03-23-2019 04:03 PM
Perhaps cin(x) need a bit more restriction, not just cin(cin(cin(x))) = sin(x)
sin(cin(x)) = cin(sin(x))
cin(x) should be an odd function, shape like sin(x), with value between sin(x) and x
For domain [-pi/2, pi/2], cin(x) ≈ (1 + x²/9) sin(x)
Example:
sin(½) = 0.4794255386
cin(cin(cin(½))) = 0.4791650974, relative error ~ -0.05%
sin(cin(½)) ≈ 0.473044
cin(sin(½)) ≈ 0.473050
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - rprosperi - 03-23-2019 09:49 PM
(03-23-2019 12:40 AM)Valentin Albillo Wrote: P.S.: What would it take to lure you into releasing a version of Emu71 which would run on a 32-bit or 64-bit Windows OS, or at least on Android ? Begging ? Bribing ? Taking some relative hostage ? Just plain ol' money ? You tell me, please, it's really affecting my productivity !!
Valentin - Emu71/DOS runs great on Win7/8/10 (including x64) operating under DOSBOX, though of course not at the full speed it would run if running as native code.
So, if by productivity you mean having to change to a DOS machine to run Emu71, then the above would save a lot of time and hassle, however if raw Emu71 execution speed is the issue, this may not be a big increase in speed, if it increases at all.
As for using Christoph's EMU71/Win, you can remove the "run at actual speed" option and have much higher speed, but I don't know how it compares to native Emu71/DOS on your machine.
If you send me a sample program with relatively long run-time, I'd be happy to time it running on my PC under both Emu71/DOS/DOSBOX and Emu71/Win at it's max speed. This is an older PC with a XEON 3GHz CPU running Win7x64, so not the fastest, but it at least provides some relative performance numbers.
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - J-F Garnier - 03-24-2019 09:08 PM
(03-22-2019 08:04 AM)J-F Garnier Wrote: Tier 5: Guru
In summary : Write a program or function cin(x) which has the defining property that cin(cin(cin(x))) = sin(x).
Once written, use it to tabulate cin(x) for x = 0.0, 0.2, 0.4, ..., 1.0
...
Still searching for a better one...
(03-23-2019 04:03 PM)Albert Chan Wrote: cin(x) should be an odd function, shape like sin(x), with value between sin(x) and x
For domain [-pi/2, pi/2], cin(x) ≈ (1 + x²/9) sin(x)
Example:
sin(½) = 0.4794255386
cin(cin(cin(½))) = 0.4791650974, relative error ~ -0.05%
sin(cin(½)) ≈ 0.473044
cin(sin(½)) ≈ 0.473050
Since cin(x) is an odd function, its Taylor expansion can be written as cin(x)=x+a*x^3+b*x^5+...
So my approach was to build the Taylor expansion of cin(cin(cin(x))) and identify it to the well known sinus expansion sin(x)=x-x^3/3!+x^5/5!...
The x^3 term is easy to calculate and is just -(1/3!)/3=-1/18, in agreement with Albert's approximation (-1/3!+1/9).
The best I could calculate (by hand) was the x^5 term. Then I search for the x^7 term by try-and-error to minimize the error.
Here is my best approximation and results showing cin(cin(cin(x))) and sin(x):
10 ! SSMC24
30 A=-1/18 @ B=-7/1080 @ C=-.0015
40 DEF FNC(X)=X+A*X^3+B*X^5+C*X^7
50 FOR X=.1 TO 1 STEP .1
60 PRINT X;FNC(FNC(FNC(X)));SIN(X)
70 NEXT X
> RUN
.1 9.98334166706E-2 9.98334166468E-2
.2 .198669334313 .198669330795
.3 .295520279883 .295520206661
.4 .38941902196 .389418342309
.5 .479429531682 .479425538604
.6 .564659801456 .564642473395
.7 .644278060315 .644217687238
.8 .717533814261 .7173560909
.9 .783784102052 .783326909627
1 .842523170608 .841470984808
Another approach?
J-F
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Oulan - 03-25-2019 09:19 AM
Extending the approach of JF, you can use the following HP prime program
--------------------
#pragma mode( separator(.,
integer(h32) )#cas
reduc(l,n):= BEGIN
LOCAL m;
m:=MAKELIST(0,z,0,n);
FOR Z FROM 0 TO n DO
m[n+1-Z]:=l[SIZE(l)-Z];
END;
RETURN m;
END;
fff():= BEGIN
LOCAL l,m,n,z,p,q,r;
LOCAL a15,a13,a11,a9,a7,a5,a3;
PURGE(a15,a13,a11,a9,a7,a5,a3);
z:={a15,0,a13,0,a11,0,a9,0,a7,0,a5,0,a3,0,1,0};
n:=15;
p:=poly2symb(z,x);
r:=poly2symb(z,y);
FOR Y FROM 1 TO 2 DO
q:=(p|x=r);
l:=symb2poly(q,y);
l:=reduc(l,n);
p:=poly2symb(l,x);
END;
m:=MAKELIST(0,Z,0,n);
FOR Z FROM 0 to n DO
IF (Z MOD 2) = 1 THEN
m[n+1-Z]:=((-1)^FLOOR(Z/2))/(Z!);
END;
END;
PRINT(l);
PRINT(m);
a3:=eval(solve(l[n-2]=m[n-2],a3)[1]);
// was a3:=solve(l[n-2]=m[n-2],a3);
a5:=eval(solve(l[n-4]=m[n-4],a5)[1]);
a7:=eval(solve(l[n-6]=m[n-6],a7)[1]);
a9:=eval(solve(l[n-8]=m[n-8],a9)[1]);
a11:=eval(solve(l[n-10]=m[n-10],a11)[1]);
a13:=eval(solve(l[n-12]=m[n-12],a13)[1]);
a15:=eval(solve(l[n-14]=m[n-14],a15)[1]);
RETURN [a3,a5,a7,a9,a11,a13,a15];
END;
#end
--------------------
to compute the coefficients of the taylor serie of CIN(x).
Use it in CAS mode : " k:=fff() 'enter' ", then " k 'enter' "
Be careful this program will take some times on a real Prime.
But the converging is very slow, coefficient up to x^15 follows but give only 10^-6 error near 1
-1/18 -7/1080 -643/408240 -13583/29393280 -29957/215550720 -24277937/648499737600 -6382646731/953294614272000
Btw can someone explain the warning displayed when solving for the coefficients ?
"Warning, ^ is ambiguous on non square matrices. Use .^ to apply ^ element by element."
I don't see any matrices solving here ... ok I saw the problem see listing. Sometimes list of list are not displayed with all brackets.
Anyway, there should be a better approach to solve this nice challenge
EDIT new version of program, avoid computing useless power
#pragma mode( separator(.,
integer(h32) )#cas
mulT(a,b):= BEGIN
LOCAL n,p,j,k;
n:=SIZE(a);
p:=MAKELIST(0,j,1,n);
FOR j FROM 1 TO n DO
FOR k FROM 1 TO n+1-j DO
p[j+k-1]+=a[j]*b[k]; // test removed Thanks Albert
END;
END;
RETURN simplify(p);
END;
fff2(n):= BEGIN
LOCAL cin,ccin,si;
LOCAL p,q,xn,s;
LOCAL lvar,lexpr;
LOCAL a3,a5,a7,a9,a11,a13,a15,a17;
LOCAL a19,a21,a23,a25,a27,a29,a31,a33;
LOCAL a35,a37,a39,a41,a43,a45,a47,a49;
LOCAL vars;
PURGE(a3,a5,a7,a9,a11,a13,a15,a17);
PURGE(a19,a21,a23,a25,a27,a29,a31,a33);
PURGE(a35,a37,a39,a41,a43,a45,a47,a49);
PURGE(x,y);
vars:={1,a3,a5,a7,a9,a11,a13,a15,a17,a19,a21,a23,a25,a27,a29,a31,a33,a35,a37,a39,a41,a43,a45,a47,a49};
cin:=MAKELIST(IFTE(p MOD 2,vars[(p+1)/2],0),p,0,n);
ccin:=cin;
FOR q FROM 1 TO 2 DO
s:=MAKELIST(0,p,0,n);
s[1]:=ccin[1];
xn:=cin;
FOR p FROM 2 TO n+1 DO
s:=s+ccin[p]*xn;
IF p<=n THEN xn:=mulT(xn,cin);END;
END;
ccin:=s;
END;
si:=MAKELIST(IFTE(p MOD 2,((-1)^FLOOR(p/2))/(p!),0),p,0,n);
lvar:=MAKELIST(cin[p],p,4,n+1,2);
lexpr:=MAKELIST(ccin[p]=si[p],p,4,n+1,2);
s:=solve(lexpr,lvar);
RETURN s[1];
END;
#end
use with ff2(2*n+1) n from 2 to 24 (fff2(29) start to be long on a real G2), fff2(49) take few seconds on a virtual one.
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Oulan - 03-25-2019 04:27 PM
Perhaps applying some series acceleration techniques such as Romberg-Richardson or Aitken could help ...
P.S. at least try to compute on an HP hand-held device those Taylor coefficient
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Gerson W. Barbosa - 03-25-2019 09:01 PM
hp 33s
C0001 LBL D
C0002 ENTER
C0003 ENTER
C0004 2
C0005 /
C0006 COS
C0007 SQRT
C0008 *
C0009 RTN
0.2 XEQ C XEQ C XEQ C -> 1.985105083E-01
0.5 XEQ C XEQ C XEQ C -> 4.7756191243E-1
1.0 XEQ C XEQ C XEQ C -> 8.4122242185E-1
At least this is a tiny program...
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Albert Chan - 03-25-2019 09:53 PM
Calculate cin(x) taylor coefficients with XCas. Only need adjust vars for more terms.
vars := [a3, a5, a7, a9, a11, a13, a15];
n := 2*len(vars) + 1;
y := x + sum(vars(k) * x^(2*k+1), k, 1, (n-1)/2);
cin(x0) := subst(y, x=x0);
solve(coeff( taylor(cin(taylor(cin(cin(x)), x, n)) - sin(x), x, n, polynom), x) = 0, vars)
→ [-1/18, -7/1080, -643/408240, -13583/29393280 ...]
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Valentin Albillo - 03-28-2019 12:38 AM
Hi, all:
First of all, thanks to all 5 of you who contributed to this thread so far, namely Albert Chan, Paul Dale, J-F Garnier, Oulan and Gerson W. Barbosa, your efforts and interest are much appreciated (and also thanks for not using CODE sections as I requested).
A week has elapsed and now I'll post my original solutions and comments to the different tiers discussed, one at a time, beginning with Tier 1:
Tier 1 - The Challenge:
We'll call Homage Number to any 10-digit positive integers which are multiples of 271, divisible by 41 and further their digits are all distinct. Write a program that takes no inputs but simply finds out and outputs just how many Homage Numbers there are.
My original solution:
This tier was expressly created to be really easy so anyone interested could write code to solve it without much trouble. Matter of fact, as Albert Chan realized, it can be solved by hand with just a little thinking. The key is to realize that 41 and 271 are coprime, so every Homage number should be divisible by both and thus by their product, which is 41 * 271 = 11,111.
Also, being a 10-digit number and having all its digits distinct means that its digits are 0, 1, 2, 3, ... , 9 in some order and thus their sum is 1 + 2 + 3 + ... + 9 = 45, which is divisible by 9 so each Homage number has to be divisible by 9 too. As 9 is coprime to 41 and 271, each Homage number N must be divisible by their product, i.e., by 41 * 271 * 9 = 99,999.
Now let's split N into two 5-digit parts, A, B, like this: N = 100,000*A + B, which must be a multiple of 99,999, so subtracting 99,999*A from it the resulting value: 100,000*A + B - 99,999*A = A + B must be a multiple of 99,999 too and, as both A and B are 5-digit long, i.e., less than 100,000, that multiple must be 99,999 itself. Now, considering their individual digits we have:
A + B = abcde + uvxyz = 99999
and thus all 5 pairs of digits must comply with a + u = b + v = ... = e + z = 9.
Now, there are 5! permutations of the 5 pairs, so 120 permutations in all, but each of the 5 pairs has 2 possible orderings, say (a,u) and (u,a), so 25 = 32 variations for each of the 120 permutations and thus there are 120 * 32 = 3,840 potential Homage numbers in all.
However, only 9 out of 10 begin with a non-zero digit (numbers beginning with a 0 aren't 10-digits numbers) and so finally there are 3,840 * 9/10 = 3,456 Homage Numbers.
What if we can't or won't engage on such math reasoning ? Well, that's where our trusty HP calc will take away all the drudgery and work out the solution by itself, doing all the work for us in mere seconds and saving our neurons for better endeavours. In my case, this little 2-liner for the HP-71B (fits in just 1 line too) will scan the whole range at steps of 99,999, increasing the count each time the corresponding number happens to have all its 10 digits different:
1 DESTROY ALL @ C=0 @ D=99999 @ FOR N=D*CEIL(10^9/D) TO 10^10-1 STEP D
2 C=C+NOT SPAN("0123456789",STR$(N)) @ NEXT N @ DISP C
>RUN
3456
so there are 3,456 Homage Numbers in all.
That's it. Affordable, as promised. In the next days I'll post my solutions for the subsequent tiers.
V.
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Werner - 03-28-2019 11:10 AM
(03-28-2019 12:38 AM)Valentin Albillo Wrote:
Hi, all:
A week has elapsed and now I'll post my original solutions and comments to the different tiers discussed, one at a time, beginning with Tier 1:
[...]
In the next days I'll post my solutions for the subsequent tiers.
Does that mean I'll have to wait 4 more days for the solution of tier 5? Dang.
Werner
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Albert Chan - 03-28-2019 12:51 PM
Homage number 99999 divisibility trick can be used for other numbers.
Example, to do *both* mod 7 and mod 13 at the same time, for X = 20 190 328
7 * 13 = 91
100 (mod 91) ≡ 9
1000 (mod 91) ≡ 90 ≡ -1
X (mod 91) ≡ 20 - 190 + 328 ≡ 158 ≡ 9 + 58 ≡ 67
X (mod 7) ≡ 67 - 63 ≡ 4
X (mod 13) ≡ 67 - 65 ≡ 2
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Valentin Albillo - 03-29-2019 01:55 AM
Hi, all:
Let's continue with my original solutions, today it's time for:
Tier 3 - The Challenge:
Those positive real numbers that are either powers or sums of distinct powers of an arbitrary real number P form an increasing sequence whose first term is 1 (i.e.: P0). Write a program which accepts as input both P and an index k and returns the corresponding kth term in the sequence.
Use your program to find the 1,000,000th term and the 3,141,593th term when P = e as well as the 1,234,567th term and the 2,718,282th term when P = Pi.
My original solutions:
Though the concept used in this challenge will work for powers of any number P >= 2, whether integer or real, I purposefully used a sequence of real numbers which were either powers or sums of distinct powers of e instead of powers of an integer to avoid giving as examples some integer sequences that people would immediately search for in OEIS.
For instance, my preliminary (not posted) examples where based on the integer sequences for P = 3 and P = 61, namely:
1 3 4 9 10 12 13 27 28 30 31 36 37 39 40 81 ...
1 61 62 3721 3722 3782 3783 226981 226982 227042 ...
but I decided to use instead P = e and P = Pi , which generate sequences of reals not present in OEIS. That said, the key fact is that the elements which are either powers or sum of distinct powers of a base P naturally map to the elements which are either powers or sum of distinct powers of base 2, which of course are all the integers 1, 2, 3... , i.e. precisely the indexes for the elements in the base-P sequence. Thus we only need to find the base-2 expression for a given index and then interpret that base-2 expression as a number in base P, which we then convert to the usual base 10. For example:
- to find the 6th element in the sequence for P = 61:
the index 6 in base 2 = 1102 -> 11061 = 612 + 611 = 3721 + 61 = 3782 in base 10
My original solution for the HP-71B is this 68-byte 1-liner:
1 DEF FNE(N,K) @ M=0 @ P=1 @ REPEAT @ M=M+P*MOD(N,2) @ P=P*K @ N=N DIV 2 @ UNTIL NOT N @ FNE=M
and to compute the particular elements asked for in the challenge, simply:
>FNE(1000000,EXP(1))
278394444.173 { = e6 + e9 + e14 + e16 + e17 + e18 + e19 }
>FNE(3141593,EXP(1))
1601007663.31
>FNE(1234567,PI)
9091632437.43 { = Pi0 + Pi1 + Pi2 + Pi7 + Pi9 + Pi10 + Pi12 + Pi14 + Pi15 + Pi17 + Pi20 }
>FNE(2718282,PI)
30446503139.5
It's worth mentioning that for P = 8 and P = 16 there's an even simpler solution for the HP-71B right from the command line. For instance, to find the 123th element in the sequence of powers or sum of distinct powers of 8, simply execute this from the command line:
>BVAL(BSTR$(123,2),8)
299529
which of course agrees with the 1-liner: FNE(123,8) -> 299529.
Also worth mentioning is the fact that my solution also works for P < 2, even for P = 1, P = 0 and P < 0 but then the resulting sequence is no longer in increasing order as is the case for P >= 2. For instance:
P = 2 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... increasing, Ok
P = 1.9 1, 1.9, 2.9, 3.61, ..., 13.369, 13.0321, ... not increasing
P = Phi 1, 1.6180, 2.6180, 2.6180, 3.6180, ... not increasing, repetitions
P = 1 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, ... ditto
P = 0 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ... ditto
P = -1 1, -1, 0, 1, 2, 0, 1, -1, 0, -2, -1, ... ditto
P = -2 1, -2, -1, 4, 5, 2, 3, -8, -7, -10, ... ditto
Last but not least, this is my original solution for the HP-25, a simple 24-step affair:
01 STO 0 13 *
02 STO 1 14 RCL 1
03 STO/ 1 15 *
04 CLX 16 +
05 X<>Y 17 RCL 0
06 2 18 STO* 1
07 / 19 Rv
08 INT 20 X<>Y
09 X<>Y 21 X#0
10 LASTX 22 GTO 06
11 FRAC 23 X<>Y
12 2 24 GTO 00
For instance:
FIX 0
26, ENTER, 3, R/S -> 111
61, ENTER, 3, R/S -> 361
1000000, ENTER, 3, R/S -> 1726672221
So much for Tier 3, thanks a lot to Paul Dale for his interest in this particular tier and for taking the time to create a nice 24-step solution for the HP-25 as well. In the next days I'll post my solutions for the subsequent tiers.
V.
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Juan14 - 03-31-2019 02:51 PM
For the last challenge.
Let cin(x) = sin(x+A), we have:
sin(sin(sin(x+A)+A)+A) = sin(x) or
sin(sin(x+A)+A)+A = x
For a given value of x, we can solve the last equation for A (A is a function of x).
Here is the program for the hp 50g:
«
→ x
«
'SIN(SIN(x+A)+A)+A-x'
'A' 1 ROOT x + SIN →NUM
»
»
x_____cin(x)
0_____0.
0.2___0.19954743606
0.4___0.39617257453
0.6___0.586447829132
0.8___0.761 006258889
1_____0.906981195071
π/2____.835085096711
-0.71__-0.684625012855
2.019__4.81961624069E-3
There are so many ways to define the function cin(x) in a similar way, that's why I didn't post my solution before, but here it is anyway :-)
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Albert Chan - 03-31-2019 03:26 PM
(03-31-2019 02:51 PM)Juan14 Wrote: For the last challenge.
Let cin(x) = sin(x+A), we have:
sin(sin(sin(x+A)+A)+A) = sin(x) or
sin(sin(x+A)+A)+A = x
For a given value of x, we can solve the last equation for A (A is a function of x).
Nice try, but identity cin(cin(cin(x))) = sin(x) does not hold
Example, with above cin(x) definition, and x = 1.0
sin(1) ≈ 0.841471
cin(cin(cin(1))) ≈ cin(cin(0.906981)) ≈ cin(0.844196) ≈ 0.796542
Even worse if x=Pi/2
sin(Pi/2) = 1
cin(cin(cin(Pi/2))) ≈ cin(cin(0.835085)) ≈ cin(0.789340) ≈ 0.752222
RE: [VA] Short & Sweet Math Challenge #24: "2019 Spring Special 5-tier" - Albert Chan - 03-31-2019 10:11 PM
(03-21-2019 02:08 AM)Valentin Albillo Wrote: Tier 4: Advanced
[MRM: HP-11C and up]
Consider the n-point dataset (xi , yi) where xi = 1, 2, 3, 4, 5, 6, ..., n (the natural numbers) and yi = 2, 3, 5, 7, 11, 13, ..., pn (the prime numbers), and the (n-1)st degree polinomial fit to this dataset of the form:
P(x) = a0 + a1 (x-1) + a2 (x-1) (x-2) + ... + an-1 (x-1) (x-2) (x-3) ... (x-(n-1))
Getting sum of above coefficients can be done by doing forward difference of the primes:
2 3 5 7 11 13 17 19 23 29 ... ; primes
1 2 2 4 2 4 2 4 6 ... ; Δ
1 0 2 -2 2 -2 2 2 ... ; Δ²
-1 2 -4 4 -4 4 0 ... ; Δ³
3 -6 8 -8 8 -4 ... ; Δ4
...
ak = Δk(0) / k!
Σ(ak, k = 0 to Inf) = 2/0! + 1/1! + 1/2! - 1/3! + 3/4! + ...
Sum converge very fast:
2.0
3.0
3.5
3.33333 333333
3.45833 333333
3.38333 333333
3.41527 777778
3.40476 190476
3.40761 408730
3.40696 097884
3.40708 691578
3.40706 684905 ; 6 digits accuracy with 12 primes
3.40706 938140
3.40706 915834
3.40706 916344
3.40706 916625
3.40706 916552
3.40706 916564
3.40706 916563 ; 12 digits accuracy with 19 primes