The Coding Thread

[Ex-User (14663)]

What about a little thread where we post and solve small, cool problems to be solved computationally?

I'll kick things off with this one:

Write a function that computes the sum of the n first Fibonacci numbers. Print some cases, e.g. n =10, n = 100, n = 10,000. Preferably explain the idea of the algorithm as well

 

[Cognisant]

I'm confused, you want a Fibonacci sequence that starts with something other than 1 (lets call that 'x') and goes to n?

So if 'n' = 10.5 then 'x' = 0.5

Spoiler

0.5
0.5
1
1.5
2.5
4
6.5
10.5
17

But the thing is if 'n' is 10 or 10.5 or basically any number that isn't part of the usual sequence then I don't think the reverse sequence is ever going to stop so there will be no "first" number.

I just pulled 0.5 out of my ass and calculated up.

 

[Ex-User (14663)]

no, I mean the usual Fibonacci numbers. So n is an integer.

If it's the 10,000 that's confusing you it's supposed to be 10000, not 10.000. I hear they like to use commas to separate zeros over there in US so I went with that.

 

[Black Rose]

fibsum = 0
x = 0
y = 1
z = 0

for loop 5{

z = x + y
x = y
y = z

fibsum += z

return z}

print fibsum: 19

1, 2, 3, 5, 8 end

 

[Ex-User (14663)]

lol I just realized n=10000 might be a bit ambitious. It makes for an interesting challenge though

 

[Turnevies]

function fs =FibSum(n)
phi=0.5*(1+sqrt(5)); %golden ratio
fibvec=1:n;
fibvec=(phi.^fibvec)/sqrt(5);
fibvec=round(fibvec); %The fibonnaci numbers
fs=sum(fibvec);
end

I found a closed expression for fibonacci numbers on wikipedia. Vectorized the code for efficiency, and let it run in matlab.

Calculation performed in ~8e-4 sec. on my laptop shows that FibSum(1000)=1.1380e+209.
FibSum(10000) doesn't take longer, but gives infinity as a result. There must be a way to keep the result finite I guess by playing with different number representations or so, but I suppose that for all kinds of practical purposes this number is effectively infinity anyway.

 

[gps]

Fibonacci Sequence at Rosetta Code

I suppose this is a good place to introduce memoization into the conversation ... especially when one arbitrarily picks n=10000.

Anaphoric programming might be applied to generating the fibonnaci sequence as well as streams.

It would be nice if TryScheme, TryAPL, and others allowed one to represent a runnable program as a link, but Papert Logo does, so ... To generate and see a Fibonacci sequence, Click me!

 

[gps]

FibSum(10000) doesn't take longer, but gives infinity as a result. There must be a way to keep the result finite

Enter the notions of bignums and arbitrary-precision arithmetic.

 

[Ex-User (14663)]

A little solution I put together last night. The idea is pretty straightforward; since we're dealing with big numbers, I use vectors of digits to represent them. To add them I use the good ol' manual addition method we all learned as small kids. The rest is pretty much the usual Fibonacci sequence generation as in Anime's post.

Spoiler

#include <vector>
#include <iostream>

typedef std::vector<short int> lint;


lint add_lints(const lint &x, const lint &y){
    size_t xlen = x.size(), ylen = y.size();
    size_t M = ylen > xlen ? ylen : xlen;

    lint sum(M + 1);

    size_t xpos = xlen - 1, ypos = ylen - 1;
    short int s_carry = 0, xi, yi, s;

    for(int i = M; i != -1; --i){
        xi = xpos < 0 ? 0 : x[xpos--];
        yi = ypos < 0 ? 0 : y[ypos--];
     
        s = xi + yi + s_carry;
        s_carry = s / 10;
        s %= 10;

        sum[i] = s;
    }
    return sum;
}


lint fibsum(const int n){
    const int m = n / 10;

    lint x1(m, 0), x2(m, 0), x3(m, 0), s(m, 0);
    x1[m-1] = x2[m-1] = 1;
    s[m-1] = 2;

    for(int i = 2; i != n; ++i){
       x3 = add_lints(x1, x2);
       x2.swap(x1);
       x2 = x3;
       
       s = add_lints(s, x3);
    }
    return s;
}




void printvec(const lint &x){
    for(int i = 0; i != x.size(); ++i){
       std::cout << x[i];
    }
    std::cout << std::endl;
}

int main(){
    
    lint s10 = fibsum(10);
    lint s100 = fibsum(100);
    lint s1000 = fibsum(1000);
    lint s10000 = fibsum(10000);        
    
    printvec(s10);
    std::cout << "\n\n" << std::endl;
    printvec(s100);
    std::cout << "\n\n" << std::endl;
    printvec(s1000);
    std::cout << "\n\n" << std::endl;
    printvec(s10000);
    return 1;
}

output:
n = 10: 143
n = 100: 927372692193078999175
n = 1000:

Spoiler

113796925398360272257523782552224175572745930353730513145086634176691092536145985470146129334641866902783673042322088625863396052888690096969577173696370562180400527049497109023054114771394568040040412172632375

n=10000:

Spoiler

88083137989997064605355872998857923445691333015376030932812485815888664307789011385238647061572694566755888008658862476758094375234981509702215595106015601812940878487465890539696395631360292400123725490667987980947195761919733084221263262792135552511961663188744083262743015393903228035182529922900769207624088879893951554938584166812233127685528968882435827903110743620870056104022290494963321073406865860606579792362403866826411642270661211435590340090149458419810817251120025713501918959350654895682804718752319215892119222907223279849851227166387954139546662644064653804466345416102543306712688251378793506564112970620367672131344559199027717813404940431009754143637417645359401155245658646088296578097547699141284451819782703782878668237441026255023475279003880007450550868002409533068098127495095667313120369142331519140185017719214501847645741030739351025342932514280625453085775191996236343792432215700850773568257988920265539647922172315902209901079830195949058505943508013044450503826167880993094540503572266189964694973263576375908606977788395730196227274629745722872833622300472769312273603346624292690875697438264265712313123637644491367875538847442013130532147345613099333195400845560466085176375175045485046787815133225349388996334014329318304865656815129208586686515835880811316065788759195646547703631454040090435955879604123186007481842117640574158367996845627012099571008761776991075470991386301988104753915798231741447012236434261594666985397841758348337030914623617101746431922708522824868155612811426016775968762121429282582582088871795463467796927317452368633552346819405423359738696980252707545944266042764236577381721803749442538053900196250284054406347238606575093877669323501452512412179883698552204038865069179867773579705703841178650618818357366165649529547898801198617541432893443650952033983923542592952070864044249738338089778163986683069566736505126466886304227253105034231716761535350441178724210841830855527586882822093246545813120624113290391593897765219320931179697869997243770533719319530526369830529543842405655495229382251039116426750156771132964375

By no means an efficient implementation, but runs in a second or two.

There should probably be a way of reducing the no. of operations by noting that e.g.
21 + 13 + 8 + 5 + 3 + 2 + 1 + 1 = 2(21) + 2(5) + 2

 

[gps]

There should probably be a way of reducing the no. of operations by noting that e.g.
21 + 13 + 8 + 5 + 3 + 2 + 1 + 1 = 2(21) + 2(5) + 2

It seems that you're trying for a `recurring pattern' exploit not generalizable to similar or related problems ... such as factorial, markov chains, and such.

I suspect that a `solution' in which 1 x fib(n) rectangles are stacked side-by-side would help the human eye see/spot the common factors.
The difference between prime factorization and the sort we'd want to use here is that prime factorization entails multiplication whereas in this case we want to represent sums as the sum of two or more integers with one of these integers being the sum of the previous stage.

(note: if we were going to be using this algorithm A LOT -- such as in some cyrptographic algorithm -- it might bear such computational optimization. I suspect that it's performance above and beyond an algorithm using memoization would end up not worth the optimization effort.)

Dynamic languages (python, ruby, javaScript, all the lisps, etc.) offer an exploit in the form of `eval' which allows a `program' or symbolic expression to be programatically composed/constructed THEN evaluated at run time.

As the lisps (including Scheme implementations and some Logos) allow both addition and multiplication to be performed en mass -- rather than pasting arguments together pairwise as per infix inflix notation -- what we think of as an integer MAY be re-presented as subexpressions which evaluate to those integers.
To wit:
1 + 2 ==> (+ 1 2)
1 + 2 + 3 ==> (+ 1 2 3)

21 + 13 + 8 + 5 + 3 + 2 + 1 + 1 ==> (+ 21 13 8 5 3 2 1 1)
OR, via the magic of both infix and dynamic evaluation
(eval (cons '+ '(21 13 8 5 3 2 1 1)))
OR, if we replace integers with expressions summing-to

; note: best viewed inside the code block so same number line up vertically.

; All of our integers can be represented as sums of integers
(+ 
   (+ 21 13 8 5 3 2 1)
        (+ 13 8 5 3 2 1)
        (+ 13 8 5 3 2 1)
             (+ 8 5 3 2 1)
                (+ 5 3 2 1)
                   (+ 3 2 1) 
                      (+ 2 1)
                         (+ 1)
                         (+) ; the additive identity
)

 

[Ex-User (14663)]

Hmm, actually, the whole thing is simpler than I thought. In fact, if you let S_n denote the sum of all Fibonacci numbers F_k for k=1, 2, ... n, then

S_n = F_{n + 2} - 1

I.e. it's just the Fibonacci number two steps ahead, minus 1. This is easy to prove using induction.

 

[Ex-User (14663)]

Have no clue if it's difficult or not (probably is) but one I thought of right now:

Compute the 10 most significant digits of (1 / pi) raised to power of 1000

 

[gps]

I.e. it's just the Fibonacci number two steps ahead, minus 1.
This is easy to prove using induction.

So ... given the theme of this/your thread, perhaps you can compose and present code in one-or-more programming languages which feature, demonstrate, or exploit `induction' as you're using the term.

As you've expressed a disdain for OOP perhaps you'd like to use one-or-more non-OOP paradigms to use code to make your point?

Personally, my own bents and proclivities find me preferring to expand the audience of this thread via accessibility breadth over math/CS formal scicneces depth.
To wit, how might one-or-more of us participants dePICT the results of this `induction' via graphico-visual means which would allow those with dominant right hemispheres to SEE what you mean while absolving them of the responsibility or multiple intelligences configuration to either follow your textual narrative or the algorithmic logic of your code ... or some blend of BOTH?

For instance, what if the unique additive factors of the Fibonacci were presented as 1xN rectangles of either RGB (EG like a 3 color map) or a unique color via, say, 24-color ... then stacked end-to-end vertically, horizontally, or such so the the human eye could readily notice what your inductive process by itself might not necessarily reveal or make apparent to such Visual Thinkers?

 

[gps]

To wit, how might one-or-more of us participants dePICT the results of ... <something or other> ... which would allow those with dominant right hemispheres to SEE what you mean while absolving them of the responsibility or multiple intelligences configuration to either follow your textual narrative or the algorithmic logic of your code ... or some blend of BOTH.

For instance, what if the unique additive factors of the Fibonacci were presented as 1xN rectangles of either RGB (EG like a 3 color map) or a unique color via, say, 24-color ... then stacked end-to-end vertically, horizontally, or such so the the human eye could readily notice what your inductive process by itself might not necessarily reveal or make apparent to such Visual Thinkers?

For example, in this all the factors are represented by rectangles having the same color AND the end-to-end stacking is equivalent to the sum of constituents lengths.
The relative numeric values of neighboring Fibonacci numbers are represented by lengths perceptible to the naked eye sans any notion of numbers ... which can trigger eyes glazing over in some people.

 

[Ex-User (14663)]

So ... given the theme of this/your thread, perhaps you can compose and present code in one-or-more programming languages which feature, demonstrate, or exploit `induction' as you're using the term.

As you've expressed a disdain for OOP perhaps you'd like to use one-or-more non-OOP paradigms to use code to make your point?

Oh, I was referring to mathematical induction, the proof technique.

So for this case it's quite elementary. For the base case, we can see that e.g.

1 + 1 + 2 + 3 = 7

The Fib number two steps ahead of 3 is 8, and 8-1 = 7. So assuming n-case holds, we prove n + 1. This is also easy:

That's pretty much it. So basically, any algorithm which can generate large Fib numbers is sufficient to solve the problem.

 

[gps]

I.e. it's just the Fibonacci number two steps ahead, minus 1.
This is easy to prove using induction.

Hey! Do you suppose we might discover the actual value of infinity by starting with infinity+2 then subtracting 2?

Perhaps we could make a new number line centered at infinity rather than zero.
Then we could mark all the Fibonacci numbers, factorials, Hailstone sequence numbers, and such as we move away from infinity heading towards 0?

 

[gps]

Yes, `mathematical' induction as contrasted with philosophical induction and inductive reasoning.
Neither of which I'd want a curious INTP lurker of this thread to have to exclude as per whatever biases they bring as a member of the viewing audience.
I wouldn't want this hypothetical lurker to see a Sigma symbol without experiencing `meh' or outright repugnance, but -- to re-iterate, if not re-SUM-erize perhaps by re-Sigma-fying -- I'm more interested in promoting accessibility breadth than an over-specialized depth which panders to the pro forma sciences of mathematics and Comp Sci. while discouraging those motivated by curiosity to try their hand at the accessible, practical art of `coding'.

So, once again ...

"As you've expressed a disdain for OOP perhaps you'd like to use one-or-more non-OOP paradigms to use code to make your point?"

In other words, can you implement the sigma function via one-or-more languages capable of exploiting the functional paradigm ... which, arguably, IS the paradigm most `mathy' and capable of implementing both Capital Sigma and it's close-enough cousin the Capital Pi function?

I'm of the mind that had computers been available when the terms Alg-ebra and Alg-orithm forks of the name al-Khwarizmi algorithmic methods would have out-evolved merely `algebraic' -- whatever this adjective would come to mean in the shadow of algorithms -- ones.

For those unfamiliar with the functional paradigm, had we a sequence or stream of numbers 1 thru n -- as the limits of both/either the capital sigma or capital pi function -- we could apply any arbitrary function (EG even un-named functions in some languages capable of functional programming) to this sequence to obtain/generate the results we want.

I suspect many coders -- and more than a few tentative, potential coders -- can spot the deep-structural semantics underpinning the surface-structural Capital Sigma symbol when they see it.
I'll whip off a quick and dirty implementation of a function attributed to a ancient Greek for finding the distance between two dangling ends of any L-shape wanting to become a triGon via a method attributed to yet another ancient Greek.

; <-- this is a comment symbol
; the following symbolic expression (EG `code') was tested via the 
; elisp  [URL="https://en.wikipedia.org/wiki/Read%E2%80%93eval%E2%80%93print_loop"]REPL[/URL] of [URL="https://duckduckgo.com/?q=GNU+Emacs+for+Windows&t=ffsb&ia=web"]GNU Emacs for Windows .[/URL]
; With minor changes it can be made to work in Gimp's scriptfu,, 
; S7 scheme as implemented via GRACE and Common Music, 
; GUILE -- as the official scripting language of GNU and Gnome --
;  [URL="http://tryscheme.sourceforge.net/"]tryScheme[/URL]
; scheme in general -- via umpteen flavors --
; and, last but not least, Common Lisp
( ;<-- every symbolic expression begins with an opening paren
 (lambda (args) ; anonymous function taking an argument which is 
                         ; a list of arguments in this case
  (sqrt ; square root
    (apply '+ ; as a higher-order function, `apply' can be used to apply a 
                 ; lower order function -- as a cats paw -- to enlisted data
     (mapcar ; maps a function onto the first element of increasingly 
                 ; smaller instance of a list perpetually composed of the '(first ...) 
                 ; where `... = rest of list' until every element of the set-cum-list
                 ; has had the function mapped onto it.
      (lambda (n) ; first arg of mapcar. namely an anonymous function ...
        (* n n)       ; whose algorithm entails the multiplication of n by n
      ) 
       args ; second and final arg of mapcar
     ) ;mapcar
    ) ;apply
   ) ;sqrt
  ) ;lambda 
   '(3 4) ; the list of args required by out outermost lambda
) ;closing paren matching the opening paren followed by a function
;;; end of DOCUMENTED, verbose version

;v-- terse, mathy one-liner version
( (lambda (args) (sqrt (apply '+ (mapcar (lambda (n)(* n n)) args)))) '(3 4) )
;^-- terse, mathy one-liner version

;; note: for terser still, check out [URL="https://en.wikipedia.org/wiki/APL_(programming_language)"]APL[/URL], perhaps via [URL="http://tryapl.org/"]tryAPL[/URL]

;; note to Serac: for your 1 to n range check out APL's iota function:
;;v-- snarffed from: [URL]https://en.wikipedia.org/wiki/Iota[/URL]
;; In some [URL="https://en.wikipedia.org/wiki/Programming_language"]programming languages[/URL] (e.g., [URL="https://en.wikipedia.org/wiki/A%2B_(programming_language)"]A+[/URL], [URL="https://en.wikipedia.org/wiki/APL_(programming_language)"]APL[/URL], [URL="https://en.wikipedia.org/wiki/C%2B%2B"]C++[/URL], [URL="https://en.wikipedia.org/wiki/Go_(programming_language)"]Go[/URL][URL="https://en.wikipedia.org/wiki/Iota#cite_note-6"][6][/URL]) iota
;;  (either as a lowercase symbol ι or as a keyword iota) is used to 
;; represent and generate an array of consecutive integers. 
;; For example, in APL ι4 gives 1 2 3 4.
;;^-- snarffed from: [URL]https://en.wikipedia.org/wiki/Iota[/URL]
;;

;v-- terse, mathy one-liner version generalizing our function to 3 args
((lambda (args) (sqrt (apply '+ (mapcar (lambda (n)(* n n)) args)))) '(2 3 5))
;^-- terse, mathy one-liner version generalizing our function to 3 args

;v-- version pandering to those mentally mutilated by either procedural or OOP
;      both of which require the use of NAMES which induce nominalization,
;      reification and other cognitive diseases.

(fset ; function set.  Set the name of a fuction. In scheme we would use `define' 
  'Euclidean-distance-via-Pythagorean-theorem ; symbol/name to bind to 
                                                                           ; the following `value'
 (lambda (args) (sqrt (apply '+ (mapcar (lambda (n)(* n n)) args))))
) ; fset

; having attached a `handle' we can use it as we'd use built-in functions
(Euclidean-distance-via-Pythagorean-theorem '(3 4))
(Euclidean-distance-via-Pythagorean-theorem '(2 3 5))

; Space reserved for Serac's capital Sigma function
;
;
;

; space reserved for the Fibonacci algorithm of Turnevies
;
;
;
;

; space reserved for Animekitty's delta function
;
;
;

 

[Ex-User (14663)]

I've actually been meaning to learn some functional programming languages. Haven't gotten to that yet though.

However, I don't view functional programming as the alternative to OOP. For example, the implementation I wrote above is basically imperative programming not relying on any OOP principles. Writing it in C, for example, would amount to pretty much the exact same implementation sans the use of std::vector.

Also, I'm of the understanding that functional programming languages cannot be as efficient as imperative languages like C. You have to rely on recursion for example, which I imagine would be quite slow for, say, the Fibonacci problem above.

 

[Ex-User (14663)]

I'm more interested in promoting accessibility breadth than an over-specialized depth which panders to the pro forma sciences of mathematics and Comp Sci. while discouraging those motivated by curiosity to try their hand at the accessible, practical art of `coding'.
[/code]

I agree one shouldn't force mathematical/comp-science forms onto problems which strictly speaking don't require it. The problem with completely rejecting those forms, however, is that they prove to be very powerful tools for solving complex problems. I take a lot of pleasure from reducing 400 lines of code to 10 lines by finding some clever mathematical representation of a problem, and it allows me to write concise, robust and efficient solutions. When one at some point faces huge, complex problems, that method becomes the only way to do things.

 

[gps]

I agree one shouldn't force mathematical/comp-science forms onto problems which strictly speaking don't require it.

It's not an issue of `requiring' for me.
It's not that the term `cat' is REQUIRED for me get the deep structural meaning of the creature addressed by that surface-structural symbol; when the French say `chat' it's all the same to me.
I'm trying to help others express THE SAME semantics as you may have learned in metaphorical `English' class via alternate languages.
None of this is qua IS `required'; its preferential for/to me.

The problem with completely rejecting those forms, however, is that they prove to be very powerful tools for solving complex problems.

To my mind there's a palpable difference between `completely rejecting' and expressing THE SAME SEMANTICS via a wide variety of alternate notations ... of which programming languages offer such an assortment.
I responded to your use of capital sigma notation not by `completely rejecting'.
To my mind there's a palpable difference between `completely rejecting' and by providing a few clues to how the deep structural MEANING can be exploited via programming languages exploiting various paradigms ... functional as an excellent choice for the decidedly mathy examples you've thus far presented.

Rather than narrowing the universe of discourse as per what's implied by your rhetorical term `completely rejecting' I did -- and presently do -- attempt to broaden said universe of discourse and the assortment of programming languages whose `code' may be presented to all of us in the viewing audience.

I take a lot of pleasure from reducing 400 lines of code to 10 lines by finding some clever mathematical representation of a problem, and it allows me to write concise, robust and efficient solutions.

Sure! Start with a Java program which does math and re-implement it in APL
Aside: In college my APL classmates and I all created a descriptive statistics package in a single line of APL code.
I'll bet a java program implementing the same functionality would take that 400 lines of code you mentioned.

When one at some point faces huge, complex problems, that method becomes the only way to do things.

Response 1:
As I haven't done an exhaustive survey of all possible ways of `doing things', though have an eclectic assortment of familiar ways at my disposal, you'll probably find me sporting an eclectic mix rather than a `one right way' orthodoxical preference.

If you learned `math' either BEFORE or as a co-requisite to your programming/coding activities I can understand that FOR YOU there may be an ONLY WAY with which you are either familiar, comfortable, or both.

Many CS programs in the US of A were either spawned-from or glommed-onto extant math departments ... with predictable results.
MIT did things a bit differently; they glommed their CS department onto the EE department ... with un-head-binding results vis-a-vis the way math weenies do programming.
Math weenies didn't produce Scheme on a chip; math savvy engineers capable of both electrical engineering AND coding did.
Not that you'd value this as a math-centered or math-favoring coder, but I do.

I also value the pedagogical aspects of programming in that logical thinking can be promoted as a form of personal development by constructionism.
Math expressions don't function as machines as well as computer-implemented algorithms do; many can LEARN precepts and concepts either BETTER or AT ALL by crafting algorithms via `code' whereas math symbolism leaves them cold, disenchanted, and without a works-for-them means of UNDERSTANDING.

Though I have NO intention to remove math notation from YOUR toolbox, I do intend to present programming tools which others can ADD to their tool boxes.
Thus my goading of you to start with your domain of comfort and confidence and re-express the precepts and concepts you regard as `math' as `algorithms' expressed in `code' as the title of this/your thread suggests.
I presented evidence that I understand the precepts and concepts as expressed in BOTH domains; I was hoping that you might do something similar.
Though we may both obviously wax philosophical -- rather than expressing via `code' -- as the spirit moves us.


Response 2:
Have you heard of Metalinguistic abstaction?
How about Genetic Algorithms?
There are more than ONE wayS of dealing/coping with complexity and developing/generating complex systems,

If somebody simply loves math I see no reason why they can't present Maxima code, Octave, gnuplot, or such.

I'd still like to see you demonstrate mathematical induction via `code' in the programming language of your choice.

Or ... how about using recursion in a programming language to demonstrate a recursive proof in mathematics?

By way of a parting code snippet, here's how a generate a sequence of integers in my `text editor' of all things:

(number-sequence 1 10)

Here's how I'd map an arbitrary function onto a thusly obtained sequence:

(mapcar (lambda (x)(list x  (log x)  (log10 x) (* x x)(* x x x) (expt 2 x))) (number-sequence 1 10))

Oh! Here's Capital Sigma done via my `text editor':

(defun Capital-Sigma (data-points)
 "Add up the data points as if a math weenie using Capital Sigma"
 (apply '+ data-points)
)

; here's a test case which results in 55
(Capital-Sigma (number-sequence 1 10))

Would you care to morph Capital-Sigma into Capital-Pi by editing a single character, aside from the name, of course ... although without producing a proper factorial function?

To return to induction ...
I'm not sure I could demonstrate mathematical induction through programming though; I'd like to see it done.
Can you humor me?

Cheers!

 

[Ex-User (14663)]

I think in order to write a program that does inductive proofs, as with any mathematical proofs, it would have to be written in something that can do symbolic operations. Maybe Maxima might be a candidate for that. I really cannot think of any way you can do an inductive proof numerically.

 

[gps]

I think in order to write a program that does inductive proofs, as with any mathematical proofs, it would have to be written in something that can do symbolic operations. Maybe Maxima might be a candidate for that. I really cannot think of any way you can do an inductive proof numerically.

We're on the same page, my friend.

This being a coding thread, if one were to use code snippets employing iteration -- though perhaps not recursion, as this is what Maxima uses -- one may very well NOT be able to exploit the methods underpinning would-be `mathematical' induction; thus my intuition that visualization methods -- perhaps generated via iteration -- might generate graphics which induce iNtuitive insights on par with induction.

To wit, what if a rectangle were dePICTed which represents the n+2 term of your Capital Sigma expression merely deSCRIBEs?
What if another -- different colored rectangle -- were to represent the n+1 term?
What if a progression of these juxtapositions were presented side-by-side all the way down to n=1?
I suspect that many necessarily-subjective beholders -- INTPs among them/us -- would behold the same semantic as that encoded in your mathematically inductive surface-structural RHETORIC.
I'm of the mindset that visual presentations SHOULD be granted equal status to rhetorical exposés
presented in either `English' or any of the various notations used by math weenies.
I also suspect that graphical rhetoric is more accessible over a broader range of INTPdom.
Thus are my intuitive biases.

 

[gps]

To get back to `code'

; -*- org -*-
*    [[[URL="https://en.wikipedia.org/wiki/Induction-recursion]"]https://en.wikipedia.org/wiki/Induction-recursion ][/URL][Induction-recursion]]

^-- for those familiar with Un*x-style first-line-of-file conventions AND with emacs installed, the accession of this snippet-inserted-into-a-file just might launch emacs, insert the file in a buffer, and set the mode for the buffer to org-mode which will allow the user to simply click on the hyptertext link to have a new browerser tab launched.

Those robust enough to copy-then-paste the URL into the address bar of their web browser of choice may choose to do so.

 

[gps]

... problems to be solved computationally?

Given that computation can be used to perform symbolic computation I'll recommend this freebie which I've used personally.

Though symbolic computation as a generic concept might be useful for coders who haven't tried it yet.

 

[Ex-User (14663)]

Hmm, maybe I should learn Common Lisp. I was thinking of Haskell but Lisp looks more useful

 

[gps]

Hmm, maybe I should learn Common Lisp.
I was thinking of Haskell but Lisp looks more useful

Haskell seems for ideologues.
One seems trapped on a metaphysical side of a chasm of where monads ARE merely metaphysical.
Then one has to find a way to manifest a side-effect in the PHYSICAL World which most Real Worlders would think of as output.

The lisps tend to support multiple programming paradigms;
one can mix and match functional, OOP, imperative, declarative, and such.
If one is sufficiently self-disciplined and artistic enough to choose which paradigm to exploit at which which part in a program or a project then multi-paradigm languages are A way to go.

When I started using Touretsky's book back in '96 I was only familiar with the Logo member of the Lisp family and had AMX Lisp available to me via my Amiga.
Since then I've worked with several Schemes -- the uncommon lisps -- and Emacs Lisp.

Given your comfort and familiarity with mathematics I'd recommend The Algorithmic Language Scheme over Common Lisp for doing the exercises in the recommended book ... if you decide to use it.
The Lisps maintain two name spaces, one for functions and another for data structures; the schemes better implement the spirit of Lisp -- in which functions and data are thinly veiled versions of the same stuff -- by using ONLY one name space.

As I use emacs as my text editor for editing, I've also got a form of lisp available for pimping out said editor as I'm editing Lisp, scheme, logo ... whatever.

If you need any more incentive for learning Scheme over Common Lisp, Scheme is used as a small footprint macro & scripting language for several apps.
As I've noticed Ubuntu as your OS, you might use GIMP ... which uses the ScriptFu dialect of lisp as it's scripting/macro language.
GUILE is also a dialect of Lisp and runs on all the distros of linux.
Guix is a package manager based on scheme.

In daily practice I use emacs lisp more than scheme as emacs lisp is a domain-specific language which allows one to automate text editing functionality via lisp. For example, I can both generate a post and parse-into-paragraps-lines-and-words a post via elisp more simply than with either common lisp or scheme.
Though maybe Edwin, as distributed with MIT scheme, can do these sorts of things nearly as well; I don't really know.

So ... Scheme might be better than Common Lisp for satisfying your objectives ... depending on what they all are.

 

[gps]

Mathematical induction nested inside a Recursive Definition?

Koch snow flake as dePICTed in the link above.

 

[gps]

From the Wikipedia page
"A recursive definition (or inductive definition) in mathematical logic and computer science is used to define the elements in a set in terms of other elements in the set (Aczel 1978:740ff).

A recursive definition of a function defines values of the functions for some inputs in terms of the values of the same function for other inputs. For example, the factorial function n! is defined by the rules

0! = 1.
(n+1)! = (n+1)·n!.

This definition is valid for all n, because the recursion eventually reaches the base case of 0. The definition may also be thought of as giving a procedure describing how to construct the function n!, starting from n = 0 and proceeding onwards with n = 1, n = 2, n = 3 etc.."



So by way of code, I'll present a recursive definition of the factorial function

; emacs lisp which can readily be converted to Scheme
(fset
 (function factorial)
  (lambda  (n) ;  https://en.wikipedia.org/wiki/Factorial
   "factorial of integer n, computed recursively as per mathematical induction and algorithmic recursion"
   (if (= n 0) 
     1 ; first clause of `if' is the true option, when n=0
     (* n (factorial (- n 1))) ; 2nd clause of is is the false option
                                        ; this will recurse until n=0
   )
  ) ;lambda
)

(insert "\n\n;;; Results ==> " 
 (prin1-to-string 
  (mapcar 
   'factorial 
  (number-sequence 0 6)
  )
))
 ;;; Results ==> (1 1 2 6 24 120 720)

; emacs lisp which can readily be converted to Scheme
;  syntactic sugar option.  we can use ! as a function name
(fset
 (function !) ; ; https://en.wikipedia.org/wiki/Factorial
  (lambda  (n)
   "factorial of integer n, computed recursively as per mathematical induction and algorithmic recursion"
   (if (= n 0) 
     1
     (* ; multiplication function
       n                ; n of our mathematical induction expression
       (! (- n 1))   ; !(n -1) via the magic of a recursive call which
                         ; terminates when n=0
     );*
   )
  ) ;lambda
)

(insert "\n\n;;; Results ==> " 
 (prin1-to-string 
   (mapcar ; is a higher-order function which allows us to 
                 ; use the following function as a cats-paw 
    '! ; we'll map factorial onto a list of integers ranging from ...
    (number-sequence 0 6) ; 0 and 6, inclusive
)))

;;; Results ==> (1 1 2 6 24 120 720)

If anybody is interested I can code this via papert logo, scheme, and probably even Common Lisp ... which I've tended to avoid in favor of emacs lisp and scheme.

 

[Ex-User (14663)]

For a perhaps slightly more challenging recursive formula, how about computing the square root of 2 as a continued fraction?

 

[gps]

For a perhaps slightly more challenging recursive formula, how about computing the square root of 2 as a continued fraction?

Are you going to lead by example and present some recursive code in the language of your choice to demonstrate that you CAN use mathematical induction via recursion?

Here's a lisp function to help math weenies via domain-specific language which panders to their standard symbol `k' to mean `integer':

; emacs lisp

 ; note that predicates resulting in true-false answers typically end with
 ;     `p' via the lisps proper as contrasted with scheme dialects of the lisps,
 ;    whereas scheme notation uses the `?' suffix, thus `integer?' as a 
 ;    transliteration of the `integerp' of the lisps proper

(defun k? (n)
 "Is k a member of `integer'?"
 ; (numberp n) ;<-- We'd use this to test if any kind of number
 (integerp n)
)

; test k?  from 1 to 2 by 0.5 increments
(insert "\n;;; results ==>\t"(pp-to-string (mapcar (lambda (n) (cons n (k? n))) (number-sequence 1 2 0.5))) "note that 2.0 to the lisp REPL is a `real' rather than an integer")
;;; results ==>    ((1 . t)
 (1.5)
 (2.0))

; ref: http://sicp.ai.mit.edu/Fall-2004/manuals/scheme-7.5.5/doc/scheme_5.html#SEC43
; Scheme code goes here, ya lazy bastards!
;
;  hint: one can develop such code via: http://tryscheme.sourceforge.net/
;         along with javaScript if one is so inclined.
;
;

I'm holding off on finishing then presenting the double factorial function I started coding.
If no participant in this thread expresses an overt interest I'm not going to waste my time in the hope that one-or-more lurkers will benefit by it in some way.

Frankly these mathy numerical examples bore the ass off me.
If I'm using emacs lisp to `code' there is more sexy -- to me -- stuff I could be demonstrating than dorky numerical methods requiring or entailing mathematical induction.

 

[Ex-User (14663)]

Frankly these mathy numerical examples bore the ass off me.
If I'm using emacs lisp to `code' there is more sexy -- to me -- stuff I could be demonstrating than dorky numerical methods requiring or entailing mathematical induction.

Well, you're welcome to pose interesting problems yourself. I would hope I'm not the only one here capable of that

Here is a recursive implementation of the square-root of 2 thing in R:

sqrt2 <- function(maxdepth = 10){

    f <- function(depth){
        if(depth == maxdepth)
            2
        else
            2 + 1 / f(depth + 1)
    }
    
    1 + 1 / f(1)
}

 

[gps]

Well, you're welcome to pose interesting problems yourself.
I would hope I'm not the only one here capable of that

You haven't YET!
And therein lies the rub.
None of us can anticipate the necessarily-subjective `interest' experienced by each of the participants and lurkers alike.
You seem to prefer numerical computing & mathematical induction for proofs.
@Animekitty listed things she doesn't know much about -- I believe indicating that she's curious -- as well as presenting code supportive of her interest in modeling neural nets, brains.
@Turnevies used matlab to do the fig sequence, but didn't reveal interest outside that problem
@Cognisant gave the fib sequence a try but also didn't reveal interest.
There've been close to 700 views, but that a `view' has been registered doesn't provide any feedback on WHAT -- if anything -- the viewer found interesting, useful, practical ... whatever.

However I am AWARE of what I find interesting, useful, or such from my perspective ... as well as having encountered `interest' expressed in one-or-more other threads.
So I'll proceed from this point of departure.

; launch a new tab visiting this thread via the emacs user's default web browser
   (browse-url "https://intpforum.com/showpost.php?p=578983")

 ; launch a new tab visiting this specific post via the emacs user's default web browser
(browse-url "https://intpforum.com/showpost.php?p=579726&postcount=32")

 

[Ex-User (14663)]

For something slightly more involved: a program that downloads a thread from this forum and extracts the posts in pure text form. Later on we can perhaps analyze the text itself; say, various stats like the average post length of various users, their vocabulary etc.

 

[gps]

For something slightly more involved: a program that downloads a thread from this forum and extracts the posts in pure text form. Later on we can perhaps analyze the text itself; say, various stats like the average post length of various users, their vocabulary etc.

We've thought along a locus of similar plot points and/or objectives, although from different angles.

Rather than from a thread-downward-to-post progression it might be easier in some languages to build a system which can parse a post -- bbcode tags, text, code blocks and such -- and allow one to re-present and save the parsed still-structured data in one-or-more data structures, file formats, or such.

As many apps use CSV and/or TSV to import and export data I imagine that whatever we come up with that uses these single-character delimited formats will be of more use to non-coders and coders alike.

Any meta-coding thoughts on this?

As this is a generic coding thread we'd want implementations of whatever specifications emerge via several programming languages.
I'm willing to demo code in emacs lisp; I'll leave the brainfuck implementation to others.

So ... I'm imaging voluntacracy producing code snippets available for use in top-downard, bottom-upward, and middle-outward design strategies in multiple programming languages available for use as jigsaw puzzle pieces available for application and re-use;
I'm thinking that a tower-of-babel combinatatorial explosion can manifest.

This might be a case where a language-neutral block diagram might be of use.
Not that I'm volunteering to either initiate or contribute to one, mind you.

 

[gps]

;;;       Here's one for those with easy access to one of the [URL="https://duckduckgo.com/?q=emacsen&t=ffsb&ia=web"]emacsen[/URL]
(w3m "https://intpforum.com/showthread.php?p=579756#post579756")

;note that there a many ways of accessing web pages, URLs and such.
;   w3m is one function which happened to do a pretty good job in this case.

;   eww may give better results for other pages
(eww "download emacs")

; As two different functions were used to access web `content' a separate buffer is used for each
(list-buffers)

Here's similar-enough guts re-formatted as an org-mode file

; -*- org -*-
* Here's one for those with easy access to one of the emacsen
** [[elisp:(w3m "https://intpforum.com/showthread.php?p=579756#post579756")][view this thread via emacs and w3m]]

note that there a many ways of accessing web pages, URLs and such.
   w3m is one function which happened to do a pretty good job in this case.

**   eww may give better results for other pages
[[elisp:(eww "download emacs")][use Emacs Web Wowser to launch a duckduckgo search for `download emacs']]

** [[elisp:(list-buffers)][As two different functions were used to access web `content' a separate buffer is used for each]]

 

[gps]

However, I don't view functional programming as the alternative to OOP.

Not so much `the' as `a' in some cases.
Scala was designed as an improvement upon Java by adding functional features.
Clojure allows one to (re)use Java jar files while exploiting Lisp functionality, multiprocessing, etc.

And it's not an either-or situation anyway, as one may use OOP and functional programming together.
In the world of emacs in which I play every day one can use EIEIO and CEDET
SLIB -- what clib is to C, though in the world of Scheme -- contains libraries for a couple of different ways of implementing Objects.

For example, the implementation I wrote above is basically imperative programming not relying on any OOP principles.

Writing it in C, for example, would amount to pretty much the exact same implementation sans the use of std::vector.

Also, I'm of the understanding that functional programming languages cannot be as efficient as imperative languages like C.

I suspect that members of the Scheme community would argue the point with you ... especially if/when `efficiency' were addressed from any number of prejudicial perspectives.
For instance, from a math lover's perspective in a time when computer cycles are dirt cheap and a programmers time is not, how `efficient' seems it to require the C programmer to HAVE TO perform type casting of would-be `numbers' which aren't one-to-one and onto with a mathematician's notion of integers, reals, and complex numbers ... rather than exploit the numerical tower of Scheme?

You have to rely on recursion for example, which I imagine would be quite slow for, say, the Fibonacci problem above.

As if?
Scheme, Common Lisp, and Logo ALL support iteration as well as recursion.

So if one wanted to compare iteration with recursion one could and CAN perform such experiments.
Moreover, because Scheme can be translated into C and C can be compiled to assembly language which in turn can be assembled into machine code, one can perform experiments on execution speed, resource usage, and such as metrics of `efficiency'.
Plus -- nowadays -- C and Scheme can be mixed in the same source code via GUILE; so one can obtain the best features of both.
{note: C's macros suck; The hygienic macros of Scheme do not.}


As someone who has resorted to mathematical induction it would seem that you'd be in favor of the use of recursion to manifest/implement induction within the domain of coding rather than to `factor' it out to some not-tightly-integrated side-line process.

To revisit "which I imagine would be quite slow for, say, the Fibonacci problem above." you might be interested to know that the Scheme specification REQUIRES that for an implementation of Scheme to `be' or `qualify as' such it MUST support tail recursion, which `is' or `can be' implemented as a goto at the machine language level.

So, pending experimentation, you might want to re-think your as-yet-grounded suspicion that recursion necessarily either `is' or `substantially is' slower or less-efficient than iteration ... especially when you as a coder prefer mathematical induction which can be performed via recursion.

 

[Ex-User (14663)]

R- code I used to download threads. "read_multiple_threads" is the main function.

Spoiler

require(xml2)
require(data.table)

parse_time <- function(x, today=Sys.Date()){
    x <- gsub("Today", format(today, "%dth-%B-%Y"), x, ignore.case = T)
    x <- gsub("Yesterday", format(today-1, "%dth-%B-%Y"), x, ignore.case = T)
    x <- gsub("(?<=[0123456789])(st|rd|nd|th)", "xx", x, perl = T)
    as.POSIXct(strptime(x, "%dxx-%B-%Y, %I:%M %p", tz="UTC")) - 3600
}

get_pagecount <- function(doc){
    pg_count <- 1
    pgnav_node <- xml_find_first(doc, "//div[@class='pagenav']")
    if(length(pgnav_node) > 0){
        s <- xml_text(pgnav_node)
        s <- strsplit(gsub("[\\\t\\\n\\\r]", " ", s), " ")[[1]]
        of_idx <- grep("of", s)
        pg_count <- as.integer(s[of_idx + 1])
    }
    pg_count
}


read_posts <- function(post_tables){
    posts <- data.table()
    for(tbl in post_tables){
        post_nodes <- xml_children(tbl)
        datetime <- xml_text(xml_children(post_nodes[1])[1])
        datetime <- gsub("[\\\t\\\n\\\r]", "", datetime)
        
        msg_nodes <- xml_children(post_nodes[2])
        
        #user stuff
        user_nodes <- xml_children(msg_nodes[1])
        username <- xml_text(xml_children(user_nodes[1])[1])
        if(!length(username))
            username <- NA_character_
        
        post_contents <- xml_contents(xml_children(msg_nodes[2])[3])
        msg_elements <- gsub("[\\\t\\\n\\\r]", "", grep("<", as.character(post_contents), value = T, invert = T))
        msg_elements <- msg_elements[nchar(msg_elements)>0]
        
        newpost <- data.table(user = username, 
                              datetime = parse_time(datetime), 
                              msg_text = paste(msg_elements, collapse = " "))
        posts <- rbind(posts, newpost, fill=T)
    }
    posts
}


# reads single thread
read_thread <- function(thread_id = 26945){
    Sys.setlocale("LC_TIME", "C")
    
    main_url <- "https://intpforum.com/showthread.php?t="
    doc <- read_html(paste0(main_url, thread_id))
    post_tables <- xml_find_all(doc, "//table[@id]")    
    if(!length(post_tables))
        return(data.table(user=character(), datetime =as.POSIXct(character()), msg_text = character()))
    
    thread_posts <- read_posts(post_tables)
    pgc <- get_pagecount(doc)
    if(pgc > 1){
        for(i in 2:pgc){
            next_url <- paste0(main_url, thread_id, "&page=", i)
            doc <- read_html(next_url)
            post_tables <- xml_find_all(doc, "//table[@id]")  
            thread_posts <- rbind(thread_posts, read_posts(post_tables), fill=T)
        }
    }
    thread_posts
}


# Reads threads in index range and outputs table
# with user, datetime, post text.
# 
# "wait" is no. of seconds between download of each thread
read_multiple_threads <- function(start_idx = 22000, end_idx = 26956, wait = 1){
    threads<- data.table()
    for(i in start_idx:end_idx){
        cat("reading", i, "\n")
        thread <- read_thread(i)
        thread[, thread_id := i]
        threads <- rbind(threads, thread, fill=T)
        Sys.sleep(wait)
    }
    threads
}

 

[gps]

R- code I used to download threads. "read_multiple_threads" is the main function.

Thanks for the code!
I've been wrestling with recovering from a WinBlows virus, re-installation, creation of a Multiboot USB pendrive, Linux Mint, trying to post to this group to no avail until receiving a clue from Jennywocky ... experimenting with embedding R source code in an org-mode file.


So as to not hold up possible progress by others I'll provide a template of sorts for use by whoever has Emacs and R available.
The following `code' can be inserted into a file, opened in emacs to have it interpreted as an Org outline which Supposedly allows the embedded R code to be executed.

Spoiler

* [[https://intpforum.com/showpost.php?p=580481&postcount=37][Re: The Coding Thread]]
* [[http://orgmode.org/manual/Working-With-Source-Code.html][Working with source code]]
#+BEGIN_SRC R

SRC R
require(xml2)
require(data.table)

parse_time <- function(x, today=Sys.Date()){
    x <- gsub("Today", format(today, "%dth-%B-%Y"), x, ignore.case = T)
    x <- gsub("Yesterday", format(today-1, "%dth-%B-%Y"), x, ignore.case = T)
    x <- gsub("(?<=[0123456789])(st|rd|nd|th)", "xx", x, perl = T)
    as.POSIXct(strptime(x, "%dxx-%B-%Y, %I:%M %p", tz="UTC")) - 3600
}

get_pagecount <- function(doc){
    pg_count <- 1
    pgnav_node <- xml_find_first(doc, "//div[@class='pagenav']")
    if(length(pgnav_node) > 0){
        s <- xml_text(pgnav_node)
        s <- strsplit(gsub("[\\\t\\\n\\\r]", " ", s), " ")[[1]]
        of_idx <- grep("of", s)
        pg_count <- as.integer(s[of_idx + 1])
    }
    pg_count
}


read_posts <- function(post_tables){
    posts <- data.table()
    for(tbl in post_tables){
        post_nodes <- xml_children(tbl)
        datetime <- xml_text(xml_children(post_nodes[1])[1])
        datetime <- gsub("[\\\t\\\n\\\r]", "", datetime)
        
        msg_nodes <- xml_children(post_nodes[2])
        
        #user stuff
        user_nodes <- xml_children(msg_nodes[1])
        username <- xml_text(xml_children(user_nodes[1])[1])
        if(!length(username))
            username <- NA_character_
        
        post_contents <- xml_contents(xml_children(msg_nodes[2])[3])
        msg_elements <- gsub("[\\\t\\\n\\\r]", "", grep("<", as.character(post_contents), value = T, invert = T))
        msg_elements <- msg_elements[nchar(msg_elements)>0]
        
        newpost <- data.table(user = username, 
                              datetime = parse_time(datetime), 
                              msg_text = paste(msg_elements, collapse = " "))
        posts <- rbind(posts, newpost, fill=T)
    }
    posts
}


# reads single thread
read_thread <- function(thread_id = 26945){
    Sys.setlocale("LC_TIME", "C")
    
    main_url <- "https://intpforum.com/showthread.php?t="
    doc <- read_html(paste0(main_url, thread_id))
    post_tables <- xml_find_all(doc, "//table[@id]")    
    if(!length(post_tables))
        return(data.table(user=character(), datetime =as.POSIXct(character()), msg_text = character()))
    
    thread_posts <- read_posts(post_tables)
    pgc <- get_pagecount(doc)
    if(pgc > 1){
        for(i in 2:pgc){
            next_url <- paste0(main_url, thread_id, "&page=", i)
            doc <- read_html(next_url)
            post_tables <- xml_find_all(doc, "//table[@id]")  
            thread_posts <- rbind(thread_posts, read_posts(post_tables), fill=T)
        }
    }
    thread_posts
}


# Reads threads in index range and outputs table
# with user, datetime, post text.
# 
# "wait" is no. of seconds between download of each thread
read_multiple_threads <- function(start_idx = 22000, end_idx = 26956, wait = 1){
    threads<- data.table()
    for(i in start_idx:end_idx){
        cat("reading", i, "\n")
        thread <- read_thread(i)
        thread[, thread_id := i]
        threads <- rbind(threads, thread, fill=T)
        Sys.sleep(wait)
    }
    threads
<html>
</html>
#+END_SRC

I've got some experimenting of my own to do in getting this feature to work on my system.
Have to have the R executable in a directory somewhere and establish a link to within emacs.

Once a!gain, thanks for the R code!