OEIS A244953: Ridiculous Formula - Printable Version +- 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: OEIS A244953: Ridiculous Formula (/thread-18686.html) |
OEIS A244953: Ridiculous Formula - Gerald H - 08-20-2022 10:13 AM The entry in OEIS https://oeis.org/A244953 contains the formula a(n) = 1 + n + ( 2*(1 + n) - (1 + (-1)^n)*(1 + 2*i^(n*(n+1))) )/4, where i = sqrt(-1) which I have great difficulty to believe is anywhere near the simplest solution to the problem. Can someone please suggest a simpler calculation? RE: OEIS A244953: Ridiculous Formula - Thomas Klemm - 08-20-2022 11:34 AM How about: \( \begin{align} a(n) = \frac{3n + 4 - (n \mod 4 - 2)^2}{2} \end{align} \) Code: 00 { 20-Byte Prgm } RE: OEIS A244953: Ridiculous Formula - Gerald H - 08-20-2022 11:54 AM Very nice, Thomas, thank you. LN for formula on 33s reduced from 45 to 25, & the two formulae give the same answers! RE: OEIS A244953: Ridiculous Formula - C.Ret - 08-20-2022 08:05 PM (08-20-2022 11:34 AM)Thomas Klemm Wrote: How about:\( \begin{align} a(n) = \frac{3n + 4 - (n \mod 4 - 2)^2}{2} \end{align} \) Very nice formula that will be efficient for large \( n \), but actually lead to a longer program than the simple original definition : \( a(n)=\begin{align}\sum_{k=0}^{n}mod(-k,4)\end{align} \) A001 LBL A A002 INPUT N A003 0 A004 RCL ST Y CHS 4 Rmdr + DSE ST Y GTO A004 A011 RTN Of course, this shorter version of the code need more time to compute a(n) for large n. PS: Step A002 is optional, it is just the equivalent of a "N=?" PROMPT operation. Just to remember the user to enter a real integer. RE: OEIS A244953: Ridiculous Formula - Thomas Klemm - 08-20-2022 10:35 PM We can use the following program to generate the whole sequence: Code: 00 { 6-Byte Prgm } Initialisation 0 + 3 ENTER 5 ENTER 6 ENTER Run Just hit repeatedly: R/S RE: OEIS A244953: Ridiculous Formula - John Keith - 08-21-2022 02:21 PM (08-20-2022 10:35 PM)Thomas Klemm Wrote: We can use the following program to generate the whole sequence: That's amazing, only 4 instructions! Your formula in post #2 comes out to 14 objects in RPL, which is 3 shorter than any formula that I could come up with. You may want to add it to the OEIS page since it is shorter and simpler than the formulas there. RE: OEIS A244953: Ridiculous Formula - Thomas Klemm - 08-22-2022 03:06 PM (08-21-2022 02:21 PM)John Keith Wrote: That's amazing, only 4 instructions! It's just this recursive formula: \(a(n) = a(n-1) + a(n-4) - a(n-5)\) Or then rather: \(a(n) = a(n-4) - \left( a(n-5) - a(n-1) \right) \) Quote:Your formula in post #2 comes out to 14 objects in RPL … Is this what you refer to? Code: \<< 3 OVER * 4 + SWAP Quote:You may want to add it to the OEIS page since it is shorter and simpler than the formulas there. Meanwhile it has been updated. RE: OEIS A244953: Ridiculous Formula - John Keith - 08-22-2022 04:11 PM (08-22-2022 03:06 PM)Thomas Klemm Wrote: Is this what you refer to? Yes, exactly that. Thanks for updating the formula. RE: OEIS A244953: Ridiculous Formula - DavidM - 08-24-2022 08:23 PM I know the goal here was to find the formula for a(n) instead of computing the entire sequence, but I thought I'd include this as a possible solution to creating the list a(0)..a(n) when given n as the argument. Target platform is 50g with ListExt installed: Code: %%HP: T(3)A(R)F(.); a(5000) ~10.8 seconds in exact mode, ~7.6 seconds in approximate mode. RE: OEIS A244953: Ridiculous Formula - Thomas Klemm - 08-25-2022 05:55 AM In the same spirit we can use the following in Clojure: Code: (->> [0 3 2 1] This leads to: Code: (0 3 5 6 6 9 11 12 12 15 17 18 18 21 23 24 24 27 29 30 30 33 35 36 36 39 41 42 42 45 47 48 48 51 53 54 54 57 59 60 60 63 65 66 66 69 71 72 72 75) It takes 0.032141 msecs for 5000 on a Macbook Pro. RE: OEIS A244953: Ridiculous Formula - John Keith - 08-25-2022 03:32 PM (08-24-2022 08:23 PM)DavidM Wrote: An elegantly simple program and a great demonstration of ListExt. One would expect the Clojure version to be similar since Clojure and ListExt are strongly influenced by Haskell, where it would be something like scanl (+) 0 cycle [3, 2, 1, 0]. Thanks also because I never realized that FLOOR and CEIL work with rational numbers. IP and FP do also, returning approximate numbers, whereas FLOOR and CEIL return exact integers. RE: OEIS A244953: Ridiculous Formula - DavidM - 08-25-2022 04:07 PM (08-25-2022 03:32 PM)John Keith Wrote: ...I never realized that FLOOR and CEIL work with rational numbers. I will confess that I didn't, either, until I tested this for exact/approximate mode compatibility. I initially worked on this in approximate mode and fully expected a problem at that step. I was pleasantly surprised. RE: OEIS A244953: Ridiculous Formula - Allen - 08-27-2022 12:22 PM Good morning and thank you for an interesting discussion. Thomas, nice work on the formula!! From a different approach, I arrived at a surprisingly similar routine (perhaps the exact same formula but factored differently?) that saves two steps (5 bytes) in RPL and 2 bytes in RPN by reusing the intermediate value \( \begin{align} 3n \mod 4 \end{align} \) . Originally, I spent some time trying to implement a different formula, which still might be possible, \( \begin{align} a(n) = 6 \lfloor{\frac n 4}\rfloor + \frac{7(n \mod 4) - (n \mod 4)^2}{2} \end{align} \) but arrived a something very similar to Thomas' elegant formula from last week: \( \begin{align} a(n) = \frac{3n + 4(3n \mod 4) - (3n \mod 4)^2}{2} \end{align} \) The formula looks uglier, but is slightly more efficient to calculate with only 6 mathematical operations and 2 less commands in RPL. Code:
Somehow I feel the stack lifts could be optimized here to replicate the DUP function from RPL, but I've gotten rusty during covid. Code:
or python Code:
RE: OEIS A244953: Ridiculous Formula - Thomas Klemm - 08-28-2022 02:27 PM (08-27-2022 12:22 PM)Allen Wrote: Somehow I feel the stack lifts could be optimized here to replicate the DUP function from RPL This is what I came up with: Code: 00 { 17-Byte Prgm } Thanks for your contribution. RE: OEIS A244953: Ridiculous Formula - Thomas Klemm - 08-28-2022 02:31 PM Or then longer, but saving one byte: Code: 00 { 16-Byte Prgm } RE: OEIS A244953: Ridiculous Formula - Allen - 08-28-2022 08:37 PM (08-28-2022 02:31 PM)Thomas Klemm Wrote: Or then longer, but saving one byte: Nice work! I love how combining 2 ideas saved 20% from the original program size!!! |