OEIS A228297: Need Help to Find Algorithm

09162017, 02:41 PM
Post: #1




OEIS A228297: Need Help to Find Algorithm
I can't manage to find a way of representing this series
https://oeis.org/A228297 through some formula or recursion. Would be very grateful for suggestions. 

09162017, 03:20 PM
Post: #2




RE: OEIS A228297: Need Help to Find Algorithm
http://www.poslarchive.com/math/math/pap...42139.pdf
The abstract appears to indicate that it describes the solution for the case at hand, as well as similar recurrence relations with an odd number of terms. 

09162017, 04:41 PM
Post: #3




RE: OEIS A228297: Need Help to Find Algorithm
Thank you, Thomas for your suggestion, resulting in the programme below, which does function, but for large input, eg 20, it becomes extremely slow (31.5s).
Suggestions welcome. Code: Size: 180. 

09162017, 06:27 PM
Post: #4




RE: OEIS A228297: Need Help to Find Algorithm
That paper is beyond me, and I'm not familiar with SysRPL, but here's a memoized implementation in C which is quite fast:
Code: #include <stdio.h> If you throw very large arguments at it, you may get a segmentation fault caused by the process running out of stack space. ulimit s unlimited prevents that, although the program does need O(n) memory, for the stack and the memoization array, so you're going to hit some limit eventually. 

09162017, 06:46 PM
(This post was last modified: 09162017 06:51 PM by Gilles59.)
Post: #5




RE: OEIS A228297: Need Help to Find Algorithm
Code: « > n With 0 's' STO , 5 'k' STO I get correct result for a(1) to a(5) but a(6) returns "THEN error :undefined name" What is the problem ? 

09162017, 11:24 PM
(This post was last modified: 09162017 11:25 PM by Thomas Okken.)
Post: #6




RE: OEIS A228297: Need Help to Find Algorithm
(09162017 06:46 PM)Gilles59 Wrote: I'm not familiar with the backquote notation you're using in the default case of your CASE statement (but I don't know RPL very well so that's probably just me). I replaced the backquotes with straight single quotes, and added EVAL to force the expression to be evaluated, and I changed the first case to 'n<=s' THEN 0 END Then the program works, although, like Gerald's program, it becomes too slow very quickly because of the exponentially increasing run time. You really need to memoize the calculation to keep its run time fast enough, but because of my lack of familiarity with RPL, adapting my C code is left as an exercise to the reader. :) 

09172017, 05:15 AM
Post: #7




RE: OEIS A228297: Need Help to Find Algorithm
I should say that for input N I only want the Nth element returned, not the whole series up to N, which may lead to speedier algorithms.


09172017, 11:55 AM
(This post was last modified: 09172017 11:56 AM by Gerald H.)
Post: #8




RE: OEIS A228297: Need Help to Find Algorithm
Thank you, Thomas, for your suggestion, but I fear any algorithm that uses a complicated recursion is doomed to get bogged down & be inefficient.
Similarly Gilles, a nicely small programme, but the recursions will prohibit use for large numbers. I don't think any recursive programme will be successful. 

09172017, 03:30 PM
(This post was last modified: 09172017 03:35 PM by Thomas Okken.)
Post: #9




RE: OEIS A228297: Need Help to Find Algorithm
(09172017 11:55 AM)Gerald H Wrote: Thank you, Thomas, for your suggestion, but I fear any algorithm that uses a complicated recursion is doomed to get bogged down & be inefficient. I disagree: Code: << > N I don't have a real calculator to test this on, but in m48 on my iPhone, set to emulate a 48GX at "authentic speed," this evaluates a(100) in 137 seconds. It looks like evaluating A(N) always requires evaluating all of A(1) through A(N1), so the algorithm could also be written as an iteration, which would be equivalent in terms of the calculations it performs, but probably much faster. 

09172017, 04:08 PM
Post: #10




RE: OEIS A228297: Need Help to Find Algorithm
Thomas, I installed your programme on a real 50g & have checksum A401 & size 560.5.
For input 100 the programme returned 81 in 334s. While this is the best published programme so far (we don't know what the others have & not published), I would like the range of input on the real calculator to be at least in the millions. 

09172017, 04:51 PM
(This post was last modified: 09182017 03:31 AM by Thomas Okken.)
Post: #11




RE: OEIS A228297: Need Help to Find Algorithm
(09172017 04:08 PM)Gerald H Wrote: I would like the range of input on the real calculator to be at least in the millions. That would require an algorithm that doesn't store all of A(1)...A(N). I don't know if that's possible. Iterative implementation for HP42S: Code: 00 { 134Byte Prgm } This calculates a(100) is 97 seconds, on a real HP42S. UPDATE: The program doesn't avoid tightmemory situations; it really should do CLV "REGS" before NEWMAT, and do CLX after STO "REGS", to make sure nothing is competing with REGS for the calculator's RAM. Still, even it its current form, running in Free42 on an iPhone 5s, it calculates a(2,000,000) in under a minute, so Gerald's requirement can be met, as long as you use the right equipment. :) 

09182017, 10:44 AM
Post: #12




RE: OEIS A228297: Need Help to Find Algorithm
OK, I have now stored your programme on an otherwise empty 42S (due to memory problems on the unit I customarily use) & confirm your timing for input 100 & correctness of answer.
Bravo! Given enough computing power & sufficient energy the problem may be solved, although you could add longevity to your requirements. However, I'll stick to the real 42S or 50g. As for specifications, different for different models: For 50g: Given any natural number input the correct answer is returned in a reasonable time, ie time characteristic of algorithm should be less than linear. For 42S: Given any natural number < 5*10^11input the correct answer is returned in < 20s. 

09182017, 11:39 AM
Post: #13




RE: OEIS A228297: Need Help to Find Algorithm
This Lua program seems to produce the correct sequence:
Code: for i = 1, 10000 do Conversion to a calculator is left as an exercise The % operation is mod or remainder. Pauli 

09182017, 04:34 PM
Post: #14




RE: OEIS A228297: Need Help to Find Algorithm
I have run up against a new problem.
If you use N 5 / IP to find the integer quotient of N divided by 5 on a 42S an erroneous answer is returned for large numbers, eg for 999999999999 the answer is 200000000000 whereas it should be 199999999999 I have a programme to do the calculation correctly without disturbing the stack but believe it is inefficient. Could someone suggest a more efficient programme that leaves the stack intact? Code: 0. { 29Byte Prgm } 

09192017, 05:30 AM
Post: #15




RE: OEIS A228297: Need Help to Find Algorithm
Here my programme for 42S
Store 5 in variable "5". Unreliable for input > 5*10^11. Code: 0. { 50Byte Prgm } & for 49G Code: Qs0k5 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)