Number Trick

[Michael Morris]

Today after church, a local high school math teacher showed me a neat little parlor trick. Take a look at the code below and see if you can figure out why it works (Jim, give everyone else a chance first ). Basically you take two random positive integers, although positive reals would also work, then begin summing them fibonacci style until you have ten integers. Then you sum all of them. By taking the seventh element and multiplying by 11 you will always get the correct sum. Here's the code:

import java.util.*;
public class ChetsNumberTrick {
    public static void main(String[] args) {
        Random r = new Random();
        int[] sums = new int[10];
        for (int i = 0; i < sums.length; i++) {
            if (i < 2) {
                sums[i] = r.nextInt(100) + 1;
            } else {
                sums[i] = sums[i - 1] + sums[i - 2];
            }
            System.out.println("Element " + (i + 1) + " is " + sums[i]);
        }
        int sum = 0;
        for (int i = 0; i < sums.length; i++) {
            sum += sums[i];
        }
        System.out.println("Sum of elements is " + sum);
        System.out.println("Shortcut sum is " + 11 * sums[6]);
    }
}

[Joel McNary]

Why 11? I'm not sure. I can of course prove this, but cannot explain why 11 is the magic number.
Likewise, if you do this for only 6 elements, the sum of all the elements is equal to 4 times the fifth element.
And if you do it for 14 elements the sum of all the elements is equal to 29 times the ninth element.
And Sum(18 elements) = 76 * the eleventh element

[Jim Yingst]

Don't overlook sum(4 elements) = 4 * (3rd element)
It seems as though these sorts of relationships are not terribly uncommon in this sequence. What's special about 11? Perhaps it's just that it's easy to spot a multiple of 11 - so when some mathematician was developing formulas for sums of Fibonacci series, they noticed a couple terms with 55 and 88 in them, and said "hey look - those are divisible by 11". Which was slightly more noticeable than some of the other patterns. Well, the one I cited was pretty obvious too - just kind of boring. (Unlike all the other patterns here, of course.)
Oh, yes, while we're at it:
sum(1 element) = 1 * (1st element) :roll:
[ May 25, 2003: Message edited by: Jim Yingst ]

[Michael Morris]

As a parlor trick, most mathematically inclined can come up with a multiple of 11 without pencil and paper. Just ask for the seventh element and produce the answer before they even finish the series. Real Chick Magnet stuff!

[Joel McNary]

Originally posted by Jim Yingst:
Don't overlook sum(4 elements) = 4 * (3rd element)

I overlooked that one because it isn't true.

Element    Value
----------------
1     |   a  
2     |        b
3     |   a +  b
4     |   a + 2b
----------------
SUM   |  3a + 4b
4 * E3 = 4a + 4b

For positive a and b,
3a + 4b != 4a + 4b
There only seems to be a ralationship between the sum and an element when
elements.length > 2 && elements.length % 4 == 2
Hence my citing 6, 14, and 18. (And, of couse, as you pointed out, 1 :roll: )
The real question is, given what we know, can we predict the multiple for length == 22?

Sum(count) = Element# * x
count    #    x
6        5    4
10       7    11
14       9    29
18       11   76
22       13   ?

Of course, I'm just assuming that a). There is an integral solution and b). The element in question will be number 13. These seems to be safe assumptions, however, given the pattern as seen so far.
(You can easily modify Michael's code to arive at the answer emperically. I would like to know how to arrive at the solution without the emperical test...)
[ May 25, 2003: Message edited by: Joel McNary ]

[Jim Yingst]

Sorry, I mixed up my table of Fibonacci number formulas with my table of sums of Fibonacci number formulas. Careless. I should have said
sum(3 elements) = 2 * (3rd element)

[Arjun Shastry]

From 11, I remembered that simple trick of multiplying any number by 11.Many of you many be aware of that.e.g. 4959 X 11.
1) Write the last digit first ,i,e.9
2) Write the sum of digit and its adjacent digit to its left and carryover if more than 9.In this case,W'll write 4 ,and 1 as a carry over.
3)Repeat the step 2 until you reach the leading first digit,in this case 4.
Remember ,number should be written as 04959.

[Joel McNary]

Originally posted by Jim Yingst:
Sorry, I mixed up my table of Fibonacci number formulas with my table of sums of Fibonacci number formulas. Careless. I should have said
sum(3 elements) = 2 * (3rd element)

Ah, that makes it better.
The pattern for predicting x (x = f(count) happens to be:
f(count) = 3* f(count-4) - f(count-8)
Note that since there is no closed-form formula for predicting the nth element of the Fibbonici sequence, there is no closed form formula for predicting these numbers (you just have to work on what you already know)
The Element in question is (count+4)/2
This means, of course, that for length 22, the element is question is (22+4)/2, or 13, and the number is 3*76 - 29, or 199.
The interesting thing is working backwards. If we allowed count = 2, then Element # = 3 (count + 4) / 2. This would make little sense, unles we changed out definition of the problem a little so that we are calculating the sum of the first count elements, thereby permitting elements beyound count. Solving (backwards) for x, we get x = 1 (x = 4 * 3 - 11). Therefore, the sum of the first two elements is equal to 1 * the third element.
This is just a little less insightful (and is certainly less of a Chick Magnet ) than any of the other examples, but it does fit the pattern and thereby satisfies my obsession with this problem.

[Jim Yingst]

...and is certainly less of a Chick Magnet ...
It is hard to understand why there aren't more hot babes drawn in to these discussions.

[Michael Morris]

It is hard to understand why there aren't more hot babes drawn in to these discussions.
Go figure!

[Maulin Vasavada]

yeah
i found the generalization!!!
i will post it provided i can write in on paper and scan it.
i will write a program to get f(n) for fibo things so u can make sure about the answer.
i used to love math once upon a time.
regards
maulin

[Michael Morris]

i will write a program to get f(n) for fibo things so u can make sure about the answer.
I know a high school math teacher that will be very happy to know the solution.

[Maulin Vasavada]

hi all,
here is the C code that i wrote to find out the general solution.

long sigmaFn(long n) {
        if ( n == 2 ) {
                return 2;
        } else {
                return sigmaFn(n-1) + Fn(n);
        }
}
long Fn(long n) {
        if ( n == 0 || n == 1) {
                return n;
        } else {
                return Fn(n-1) + Fn(n-2);
        }
}
main() {
        long n=17;
        long i=0;
        long fn = 0;
        long sigmafn = 0;
        long rem = 0;
        long mul = 0;
        printf("Enter the 'Count':");
        scanf("%ld",&n);
        n--;
        fn = Fn(n);
        sigmafn = sigmaFn(n);
        /*
        printf("n=%ld\n",n);
        printf("Fn=%ld\n",fn);
        printf("Fn=%ld\n",sigmafn);
        */
        for(i=n-2; i > 0; i--) {
                rem = (fn-1) % Fn(i);
                mul = (long)(fn-1) / Fn(i);
                if ( rem == 0 )  {
                        break;
                }
        }
        /*
        printf("i=%ld\n",i);
        printf("mul=%ld\n",mul);
        */
        printf("#=%ld\n",i+3);
        printf("x=%ld\n",mul);
}

here, this will fail for case 1 that is count=6. and in this specific case i observe that the 'x' is 4 which is "square root" of "2" and i 've some "magical predictions" based on my theory that might lead us to something concrete decision but i can't explain it here as i have not mentioned how did i came up with the above program?
(thats why i told that i would provide the scanned page where i have the logic to come up with the above code. i will try to do it).
regards
maulin

[Maulin Vasavada]

btw,
sorry for writing C code but i just felt 'attracted' to write this in C rather than in Java. i donno why.
regards
maulin

[Joel McNary]

Fascinating code. I played around with it for a little bit and see what it's doing, but I would love to know why it works.
For those of you who do not have a C-compiler installed (like me), here is the Java version (I renamed the function names to make it more readable to non-mathematicians)

/**
 * DOCUMENT ME!
 *
 * @author $author$
 * @version $Revision$
 */
public class FiboCalc{
    /**
     * DOCUMENT ME!
     *
     * @param n DOCUMENT ME!
     *
     * @return DOCUMENT ME!
     */
    int seriesSum(int n){
        if (n == 2){
            return 2;
        }
        else{
            return seriesSum(n - 1) + fibboniciNumber(n);
        }
    }
    /**
     * DOCUMENT ME!
     *
     * @param n DOCUMENT ME!
     *
     * @return DOCUMENT ME!
     */
    int fibboniciNumber(int n){
        if ((n == 0) || (n == 1)){
            return n;
        }
        else{
            return fibboniciNumber(n - 1) + fibboniciNumber(n - 2);
        }
    }
    /**
     * DOCUMENT ME!
     *
     * @param argv DOCUMENT ME!
     */
    public static void main(String[] argv) throws NumberFormatException{
if(argv.length != 1){
System.out.println("Useage:  java FiboCalc <length>");
}
        new FiboCalc().runCalc(Integer.parseInt(argv[0]));
    }
    /**
     * DOCUMENT ME!
     */
    public void runCalc(int n){
        int i = 0;
        int fn = 0;
        int sigmafn = 0;
        int rem = 0;
        double mul = 0;
boolean hasValue = false;
        n--;
        fn = fibboniciNumber(n);
        sigmafn = seriesSum(n);
        System.out.println("--------------------");
        System.out.println("Fn: " + fn);
        System.out.println("Sigma: " + sigmafn);
        System.out.println("--------------------");
        for (i = n - 2; i > 0; i--){
if(i == 2){
break;
}
int fni = fibboniciNumber(i);
            rem = (fn - 1) % fni;
            mul = (fn - 1) / fni;
            System.out.println("  i: " + i);
            System.out.println("fni: " + fni);
            System.out.println("rem: " + rem);
            System.out.println("mul: " + mul);
        System.out.println("--------------------");
            if (rem == 0){
hasValue = true;
                break;
            }
        }
        System.out.println("--------------------");
        if(hasValue){
        System.out.println("# = " + (i+3));
        System.out.println("x = " + mul);
}
else{
System.out.println("No value found.");
}
        System.out.println("--------------------");
    }
}

[Maulin Vasavada]

hi all,
i have scanned 5 pages where i have written the apporach i had. all the pages are scanned in GIF format and i have a winzip file created for it but how do i post here?
regards
maulin

[Joel McNary]

You can't actually post it directly here on the boards, but you can publish it to a different web site and then link to it (preferably using the [ URL ] tag.

[Maulin Vasavada]

well,
thats the essential problem i have. i dont have any URL where i can upload it. i had my school's site but now it doesn't work after i graduated
can i send it to any of you in email, who can in turn upload it on some site and use the url tag to make it available to all?
regards
maulin

[Michael Morris]

You can upload them to my company site. I set you up an account and I'll send you a private message giving you the specifics. Once you upload them, I'll link them here.

[Maulin Vasavada]

hi Michael Morris,
i uploaded the file called "theory.zip" to the location you provided.
thank you very much for the help.
let me know if you find problems in accessing the file or anything.
regards
maulin

[Michael Morris]

I tried linking the GIFs here but they were so huge I deleted the post. I'm going to convert them to jpegs and then post them.

[Michael Morris]

Here are Maulin's GIFs





Thanks again Maulin

[Maulin Vasavada]

hi all,
also to reach on more simple solution,
we can say that if we are given "count" then,
# = (count+4)/2.
e.g.
count = 6, # = 5
count = 10, # = 7
count = 14, # = 9 etc...
and from my theory after simplification of index starting from 1 instead of 0 we can derive,
constant 'x' = [F(count) -1]/F(count/2)
Where,
F(i) = is the i th term in classic fibonacci series and i starts from 1.
=>
F(1) = 0,
F(2) = 1,
F(3) = 1 etc...
count = 10, F(10) = 34, F(5) = 3 and so,
'x' = (34 - 1)/3 = 11.
count = 14 , F(14) = 233, F(7) = 8 and so,
'x' = (233-1)/8 = 29 and so on...
regards
maulin

[Piet Souris]

hi Herbal,

welcome to the Ranch and enjoy the stay!

If one sums the terms, the series of terms for a will be a Fibonacci(1, 0) and for b it will be Fibonacci(0, 1). The 7th term of the simple series is 5a + 8b, the 10th term of the sum is 55a + 88b. So I get the impression that that teacher is right...
But I had not written a Fibonacci in Stream form, so grabbed the opportunity:

public class Fibonacci {
    
    public static void main(String... args) {
        var limit = 10;
        var list = fibonacci(1, 0)
            .flatMap(p -> Stream.of(p.a, p.b)).limit(limit).collect(toList())
        ;    
        System.out.println(list);
        fibonacci(0, 1).limit(limit).forEach(System.out::print);
        System.out.println();
    }
    
    public static Stream<LongPair> fibonacci(long firstTerm, long secondTerm) {
        return Stream.iterate(LongPair.of(firstTerm, secondTerm), p -> p.next());
    }
}

class LongPair {
    public final long a, b;
    
    private LongPair(long a, long b) {
        this.a = a;
        this.b = b;
    }
    
    public static LongPair of(long a, long b) {
        return new LongPair(a, b);
    }
    
    public LongPair next() {
        return LongPair.of(a + b, a + 2 * b);
    }
    
    @Override
    public String toString() {
        return String.format("(%,d, %,d)", a, b);
    }
}