The Math behind Fibonacci Numbers

In this blog we will see how to find index of a particular number in fibonacci series and find the number at a particular index in fibonacci series

1. Find the number at a particular index in fibonacci series

The Fibonacci numbers are defined recursively by the following difference equation:

\left\{\begin{matrix} F_{n} = F_{n-1} + F_{n-2} & & & & \\ F_{1} = 1 & & & & \\ F_{0} = 0 & & & & \end{matrix}\right.

It is easy to compute the first few elements in the sequence:

0,1,1,2,3,5,8,13,21,34⋯

Derivation of the general formula

It is possible to derive a general formula for F_{n} without computing all the previous numbers in the sequence. If a gemetric series (i.e. a series with a constant ratio between consecutive terms r^n ) is to solve the difference equation, we must have

r^n = r^{n-1} + r^{n-2}

which is equivalent to

r^2 = r + 1

This equation has two unique solutions

\varphi = \frac {1 + \sqrt{5}}{2} \approx 1.61803

\frac {1 - \sqrt{5}}{2} = 1 - \varphi = - \frac {1}{\varphi } \approx -0.61803

In particular the larger root is known as the golden ratio
\varphi = \frac {1 + \sqrt{5}}{2} \approx 1.61803

Now, since both roots solve the difference equation for Fibonacci numbers, any linear combination of the two sequences also solves it

a\begin{pmatrix} \frac {1 + \sqrt{5}}{2} \end{pmatrix}^n + b\begin{pmatrix} \frac {1 - \sqrt{5}}{2} \end{pmatrix}^n

It’s not hard to see that all Fibonacci numbers must be of this general form because we can uniquely solve for a and b such that the initial conditions of F_{1}=1 and F_{0}=0 are met

\left\{\begin{matrix} F_{0} = a\begin{pmatrix} \frac {1 + \sqrt{5}}{2} \end{pmatrix}^0 + b\begin{pmatrix} \frac {1 - \sqrt{5}}{2} \end{pmatrix}^0 & \\ F_{1} = a\begin{pmatrix} \frac {1 + \sqrt{5}}{2} \end{pmatrix}^1 + b\begin{pmatrix} \frac {1 - \sqrt{5}}{2} \end{pmatrix}^1 & \end{matrix}\right.

yielding

\left\{\begin{matrix} a= \frac {1}{\sqrt{5}}\\ b= \frac {-1}{\sqrt{5}} \end{matrix}\right.

We have therefore derived the general formula for the n-th Fibonacci number

F_{n}= \frac {1}{\sqrt{5}}\bigl(\begin{smallmatrix} \frac {1 + \sqrt{5}}{2} \end{smallmatrix}\bigr)^n + \frac {1}{\sqrt{5}}\bigl(\begin{smallmatrix} \frac {1 - \sqrt{5}}{2} \end{smallmatrix}\bigr)^n

Since the second term has an absolute value smaller than 1, we can see that the ratios of Fibonacci numbers converge to the golden ratio
\lim_{n -> \infty } \frac {F_{n}}{F_{n-1}} = \frac {1 + \sqrt{5}}{2}

Python code:

def findFibIndexValue(index):
    golden_ratio = (1 + math.sqrt(5)) / 2
    return round(((golden_ratio ** index) - ((1 - golden_ratio) ** index)) / math.sqrt(5))

2. Find index of a particular number in fibonacci series

We know that
F_{n} = \frac {1}{\sqrt{5}}\left ( \varphi ^n - \hat \varphi^n \right )
where
\varphi = \frac {1}{2}\left ( 1 + \sqrt{5} \right ) and \hat \varphi = \frac {1}{2}\left ( 1 - \sqrt{5} \right )

n = round \begin{Bmatrix} \frac {logF_{n}+log\sqrt{5}}{log \varphi} \end{Bmatrix}

where “round” means round to the nearest integer. For speed of computation we should simplify this to:
n = round \begin{Bmatrix} \alpha \cdot log F_{n} + \beta \end{Bmatrix}

where the 𝛼 and 𝛽 constants are precomputed as:
\alpha = \frac {1}{log \varphi } \approx 2.078087
\beta = \frac {log \sqrt{5}}{log \varphi} \approx 1.672276

Python code:

def findFibIndex(val):
    return round(2.078087 * math.log(val) + 1.672276)

3. Count number of digits in the nth Fibonacci number

F_{n}= \frac {1}{\sqrt{5}}\bigl(\begin{smallmatrix} \frac {1 + \sqrt{5}}{2} \end{smallmatrix}\bigr)^n + \frac {1}{\sqrt{5}}\bigl(\begin{smallmatrix} \frac {1 - \sqrt{5}}{2} \end{smallmatrix}\bigr)^n

The above formula can be simplified,
F_{n} = round\left ( \frac {\varphi ^n}{\sqrt {5}} \right )
Count of digits in Fib(n)
= log_{10}F_{n}
= log_{10}\left ( \frac {\varphi ^n}{\sqrt{5}} \right )
= n \cdot log_{10}\varphi - log_{10}\sqrt{5}
= n \cdot log_{10}\varphi - \frac {log_{10}5}{2}

 

Python code:

phi = (1 + 5**.5) / 2
def numberOfDig (n) : 
    if n == 1 : 
        return 1
    return math.ceil((n * math.log10(phi) - 
                      .5 * math.log10(5)))

Perl Apache : Perl script displayed as plain text

While configuring with apache and perl cgi scripts, don’t know why index.cgi/index.pl are displayed as plain text instead of executing them.

When browser is printing code of script that means it’s unable to find the application to run the script. Below two lines should be your first steps to solve this. AddHandler will make sure files ending with .cgi and .pl to be treated as cgi scripts. And +ExecCGI option will allow to execute the script. Also make sure your script is pointing to correct perl binary location.

    AddHandler cgi-script .cgi .pl
    Options FollowSymLinks +ExecCGI

Also There are some mistakes/misconfiguration points in your httpd.conf

  • Alias line should point to cgi-bin directory where your cgi scripts are present.

ScriptAlias /cgi-bin/ “D:\webserver\cgi-bin”

  • For same cgi-bin directory following configuration should be in httpd.conf. You should replace your <Directory "D:\webserver"> part with below.
<Directory "D:\webserver\cgi-bin" />
    AddHandler cgi-script .cgi .pl
    Options FollowSymLinks +ExecCGI
    AllowOverride None  
</Directory>
  • Try running your cgi script from command line like below. It should print or run from command line first.

perl test.cgi

  • Make sure you have read-write recursive permissions to cgi-bin directory and your cgi script. And also you can create directory or file with write permissions. If not create a cgi-bindirectory at some other place where you can have write permissions and provide rather its path in alias and directory attributes in httpd.conf instead.
  • Check apache error log for exact error message every time you run into apache conf issues. It will give you good insight into the problem.

Also this link should help you.

(Extra comment, not by the original answerer: You may also need to enable the cgi module. For me, the final step to getting cgi to work on a fresh install of Apache 2 was sudo a2enmod cgi. Before I did that, the website simply showed me the contents of the script.)

sudo a2enmod cgi

Git refusing to merge unrelated histories on rebase

During git rebase origin/development the following error message is shown from git:

fatal: refusing to merge unrelated histories
Error redoing merge 1234deadbeef1234deadbeef

The default behavior has changed since git 2.9:

“git merge” used to allow merging two branches that have no common base by default, which led to a brand new history of an existing project created and then get pulled by an unsuspecting maintainer, which allowed an unnecessary parallel history merged into the existing project. The command has been taught not to allow this by default, with an escape hatch --allow-unrelated-histories option to be used in a rare event that merges histories of two projects that started their lives independently.

Kubernetes From Scratch on Ubuntu 16.04

KUBELET
This is the first and most important component in Kubernetes. Kubelet’s responsibility is to spawn/kill pods and containers on its node, it communicates directly with Docker daemon so we need to install it first. For Ubuntu 16.04 the default version of Docker is 1.12.6.

 

root@node:~$ apt-get update && apt-get install -y docker.io

root@node:~$ docker version

Client:

Version: 1.12.6

API version: 1.24

Go version: go1.6.2

Git commit: 78d1802

Built: Tue Jan 31 23:35:14 2017

OS/Arch: linux/amd64



Server:

Version: 1.12.6

API version: 1.24

Go version: go1.6.2

Git commit: 78d1802

Built: Tue Jan 31 23:35:14 2017

OS/Arch: linux/amd64

So let’s download Kubernetes binaries and run kubelet.

 
root@node:~$ wget -q --show-progress https://dl.k8s.io/v1.7.6/kubernetes-server-linux-amd64.tar.gz

kubernetes-server-linux-amd64.tar.gz 100%[==================================================================================================================================>] 417.16M 83.0MB/s in 5.1s

root@node:~$ tar xzf kubernetes-server-linux-amd64.tar.gz

root@node:~$ mv kubernetes/server/bin/* /usr/local/bin/

root@node:~$ rm -rf *

We run kubelet with –pod-manifest-path option. This is the directory that kubelet will watch for pod manifest yaml files.

root@node:~$ kubelet --pod-manifest-path /tmp/manifests &> /tmp/kubelet.log &

Let’s put simple nginx pod manifest file to that directory and see what happens.

apiVersion: v1

kind: Pod

metadata:

name: nginx

labels:

app: nginx

spec:

containers:

- name: nginx

image: nginx

ports:

- containerPort: 80

Now we can check docker ps to see that our container has been added and try to curl it:

root@node:~$ docker ps

CONTAINER ID IMAGE COMMAND CREATED STATUS PORTS NAMES

c3369c72ebb2 nginx@sha256:aa1c5b5f864508ef5ad472c45c8d3b6ba34e5c0fb34aaea24acf4b0cee33187e "nginx -g 'daemon off" 3 minutes ago Up 3 minutes k8s_nginx_nginx-node_default_594710e736bc86ef2c87ea5615da08b1_0

b603d65d8bfd gcr.io/google_containers/pause-amd64:3.0 "/pause" 3 minutes ago Up 3 minutes k8s_POD_nginx-node_default_594710e736bc86ef2c87ea5615da08b1_0



root@node:~$ docker inspect b603d65d8bfd | jq .[0].NetworkSettings.IPAddress

"172.17.0.2"

root@node:~$ curl 172.17.0.2

<!DOCTYPE html>

<html>

<head>

<title>Welcome to nginx!</title>

The b603d65d8bfd is the id of a pause container. This is an infrastructure container that Kubernetes creates first when creating a pod. Using a pause container Kubernetes acquires IP and setup network namespace. All other containers in a pod shares the same IP address and network interface. When all your containers die, this is the last container that holds whole network namespace.

This is how our node looks like now:

KUBE API SERVER
Kubernetes use etcd, a distributed database with strong consistency data model to store the state of whole cluster. API Server is the only component that can talk to etcd directly, all other components (including kubelet) have to communicate through API Server. Let’s try to run API Server with kubelet.

First we need etcd:

 
root@node:~$ wget -q --show-progress https://github.com/coreos/etcd/releases/download/v3.2.6/etcd-v3.2.6-linux-amd64.tar.gz

etcd-v3.2.6-linux-amd64.tar.gz 100%[==================================================================================================================================>] 9.70M 2.39MB/s in 4.1s

root@node:~$ tar xzf etcd-v3.2.6-linux-amd64.tar.gz

root@node:~$ mv etcd-v3.2.6-linux-amd64/etcd* /usr/local/bin/

root@node:~$ etcd --listen-client-urls http://0.0.0.0:2379 --advertise-client-urls http://localhost:2379 &> /tmp/etcd.log &

root@node:~$ etcdctl cluster-health

member 8e9e05c52164694d is healthy: got healthy result from http://46.101.177.76:2379

cluster is health

And the API Server:

root@node:~$ kube-apiserver --etcd-servers=http://localhost:2379 --service-cluster-ip-range=10.0.0.0/16 --bind-address=0.0.0.0 --insecure-bind-address=0.0.0.0 &> /tmp/apiserver.log &

root@node:~$ curl http://localhost:8080/api/v1/nodes

{

"kind": "NodeList",

"apiVersion": "v1",

"metadata": {

"selfLink": "/api/v1/nodes",

"resourceVersion": "45"

},

"items": []

}

Now we can connect kubelet to API Server and check if it was discovered by the cluster.

root@node:~$ pkill -f kubelet

root@node:~$ kubelet --api-servers=localhost:8080 &> /tmp/kubelet.log &

root@node:~$ kubectl get nodes

NAME STATUS AGE VERSION

node Ready 5m v1.7.6

root@node:~$ kubectl get pods

No resources found.

We don’t have any pods yet, so let’s create one with kubectl create -f nginx.yaml using previous manifest file.

root@node:~$ kubectl create -f nginx.yaml

pod "nginx" created

root@node:~$ kubectl get pods

NAME READY STATUS RESTARTS AGE

nginx 0/1 Pending 0 6m

Notice here that the pod hangs in Pending status – but why ? This is because we don’t yet have another Kubernetes component responsible for choosing a node for the pod – Scheduler. We will talk about it later but for now we can just create nginx2 with updated manifest that determinates what node should be used.

root@node:~# git diff nginx.yaml nginx2.yaml

diff --git a/nginx.yaml b/nginx2.yaml

index 7053af0..36885ae 100644

--- a/nginx.yaml

+++ b/nginx2.yaml

@@ -1,10 +1,11 @@

apiVersion: v1

kind: Pod

metadata:

- name: nginx

+ name: nginx2

labels:

app: nginx

spec:

+ nodeName: node

containers:

- name: nginx

image: nginx


root@node:~$ kubectl create -f nginx2.yaml

root@node:~$ kubectl get pod

NAME READY STATUS RESTARTS AGE

nginx 0/1 Pending 0 10m

nginx2 1/1 Running 0 8s

Great, so now we can see that API Server and kubelet works. This is how our node looks like now:

KUBE SCHEDULER
Scheduler is responsible for assigning pod to a node. It watches pods and assigns available nodes to those without one.

We still have nginx pod that is in Pending state from previous example. Let’s run scheduler and see what happens.

 
root@node:~$ kube-scheduler --master=http://localhost:8080 &> /tmp/scheduler.log &

root@node:~$ kubectl get pods

NAME READY STATUS RESTARTS AGE

nginx 1/1 Running 0 17m

nginx2 1/1 Running 0 17m
view raw10.sh hosted with   by GitHub
as you can see the scheduler kicks in, finds a pod and assigns it to the node. You can see it’s placement on our node schema:

KUBE CONTROLLER MANAGER
Controller Manager is responsible for managing (among others) Replication Controllers and Replica Sets so without it we can’t use Kubernetes Deployments.
Here we are going to run it and create a deployment.

 
apiVersion: apps/v1beta1

kind: Deployment

metadata:

name: nginx

spec:

replicas: 3

template:

metadata:

labels:

run: nginx

spec:

containers:

- name: nginx

image: nginx

ports:

- containerPort: 80
view rawnginx-deploy.yaml hosted with   by GitHub

root@node:~$ kube-controller-manager --master=http://localhost:8080 &> /tmp/controller-manager.log &

root@node:~$ kubectl create -f nginx-deploy.yaml

deployment "nginx" created

root@node:~$ kubectl get deploy

NAME DESIRED CURRENT UP-TO-DATE AVAILABLE AGE

nginx 3 3 3 2 7s

root@node:~$ kubectl get po

NAME READY STATUS RESTARTS AGE

nginx 1/1 Running 0 32m

nginx-31893996-3dnx7 1/1 Running 0 18s

nginx-31893996-5d1ts 1/1 Running 0 18s

nginx-31893996-9k93w 1/1 Running 0 18s

nginx2 1/1 Running 0 32m

Updated version of our node scheme:

KUBE PROXY
Kubernetes (network) proxy is responsible for managing Kubernetes Services and thus internal load balancing and exposing pods internally for other pods and for external clients.

apiVersion: v1

kind: Service

metadata:

name: nginx

labels:

run: nginx

spec:

type: NodePort

ports:

- name: http

port: 80

nodePort: 30073

selector:

run: nginx

root@node:~$ kube-proxy --master=http://localhost:8080 &> /tmp/proxy.log &

root@node:~$ kubectl create -f nginx-svc.yaml

service "nginx" created

root@node:~$ kubectl get svc

NAME CLUSTER-IP EXTERNAL-IP PORT(S) AGE

kubernetes 10.0.0.1 <none> 443/TCP 2h

nginx 10.0.167.201 <nodes> 80:30073/TCP 7s
view raw2-12.sh hosted with   by GitHub
Nginx deployment is now exposed via 30073 port externally, we can check that with curl.

 
$ doctl compute droplet list (env: st)

ID Name Public IPv4 Private IPv4 Public IPv6 Memory VCPUs Disk Region Image Status Tags

63370004 node1 46.101.177.76 10.135.53.41 2048 2 40 fra1 Ubuntu 16.04.3 x64 active

$ curl http://46.101.177.76:30073

<!DOCTYPE html>

<html>

<head>

<title>Welcome to nginx!</title>

Git: Push a new repository

create a new repository on the command line

echo "# helm-nexus" >> README.md
git init
git add README.md
git commit -m "first commit"
git remote add origin https://github.com/{username}/helm-nexus.git
git push -u origin master

…or push an existing repository from the command line

git remote add origin https://github.com/{username}/helm-nexus.git
git push -u origin master

Setting your username in Git

Git uses a username to associate commits with an identity. The Git username is not the same as your GitHub username.

You can change the name that is associated with your Git commits using the git config command. The new name you set will be visible in any future commits you push to GitHub from the command line. If you’d like to keep your real name private, you can use any text as your Git username.

Changing the name associated with your Git commits using git config will only affect future commits and will not change the name used for past commits.

Setting your Git username for every repository on your computer

  1. Open Git Bash.
  2. Set a Git username:
    $ git config --global user.name "Mona Lisa"
    
  3. Confirm that you have set the Git username correctly:
    $ git config --global user.name
    > Mona Lisa
    

Setting your Git username for a single repository

  1. Open Git Bash.
  2. Change the current working directory to the local repository where you want to configure the name that is associated with your Git commits.
  3. Set a Git username:
    $ git config user.name "Mona Lisa"
    
  4. Confirm that you have set the Git username correctly:
    $ git config user.name
    > Mona Lisa

Adventures in Elm

2017-03-19 11_30_53-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 11_32_58-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 11_33_50-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 11_34_13-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 11_35_14-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 11_36_25-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 11_37_32-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 11_38_15-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 11_40_16-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 11_43_29-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 11_43_59-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 11_44_31-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player

2017-03-19 11_47_45-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 11_45_39-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 11_48_41-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player

2017-03-19 11_49_16-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player

You can write your first elm code online here: http://elm-lang.org/examples/hello-html

Your first hello word code will look like this:

import Html 

main =
 Html.text "Hello, World!!"

Your index.html  will look like this:

Hello, World!!

You can also div as follows:

import Html 

main =
 Html.div [] [
 Html.text "Hello, World!!"]

Output will remain the same, but if you inspect the webpage, you can see the following in the source code:

2017-03-19 12_04_08-example_hello-html.png

You can convert your html code to elm here: https://mbylstra.github.io/html-to-elm/

2017-03-19 12_08_33-Photos.png

You can also add a view function

import Html 

main = view

view : Html.Html Never
view = 
 Html.div [] [
 Html.text "Hello, World!!"]

Your output will remain the same.

If you want to output your mouse position your code will look like:

import Html 
import Mouse
import Programmator

main : Program {}
main = {

init = { x=0, y=0 },
input = Mouse.moves,
view = view
} |> Programmator.viewFromOneInput

view : Mouse.Position -> Html.Html Mouse.Position
view { x , y }= 
 Html.div [] [
 Html.text ("x= "++ (toString x) ++ ", y= " ++ (toString y))]

 

2017-03-19 12_40_06-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 12_40_17-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player2017-03-19 12_40_47-GOTO2016•Advent-Download-From-YTPak.com.mp4 - VLC media player

Java 8 coding challenge : Jarvis and Seven Segments

All over the world, peoples are working on energy solution. It would be a tough time for our next generation to survive if we don’t think about solution. Tony stark is working on a new project and wants to display his project using “seven segment display – concept”. Tony Stark gave Jarvis a task to find a number from his Favorite list of number for which the energy consumption is lowest.

(Assuming that for a digit to represent Tony stark is using 7 bulbs and only those bulbs light up which are required to represent a number and rest other would be completely off.)

Help Jarvis and conserve energy.

Seven segment display – https://en.wikipedia.org/wiki/Seven-segment_display

enter image description here

Input:
First line will contain the number of test cases and for every test case first line will contain length of favorite list and the second line for a test case will contain n numbers

Output:
For every test case print the answer. If there exist more than 1 numbers for which same number of bulbs are required than output the number which occurs first in the Favorite list.

Constraints:
Test cases< 10
A[i] < 10^6
Size of list < 10^5

SAMPLE INPUT
1
5
1 2 3 4 5
SAMPLE OUTPUT
1
Explanation

Number 1 needs only two bulbs to represent.

Code:

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashMap;
 
 
 
 
public class Solution {
 
 
 public static void main(String args[]) throws IOException{
 InputReader in=new InputReader(System.in);
 PrintWriter out=new PrintWriter(System.out);
 int T=in.readInt();
 
 while(T-->0){
 long N=in.readLong();
 long min=222222222;
 long minnum=0;
 while(N-->0){
 long num=in.readCount();
 long count=in.getcount();
 if(count<min){
 min=count;
 minnum=num;
 }
 }
 out.println(minnum);
 out.flush();
 
 }
 
 out.close();
 
 }
}
 
class InputReader{
 InputStream in;
 int[] segment={6,2,5,5,4,5,6,3,7,6};
 long count=0;
 InputReader(InputStream in){
 this.in=in;
 }
 
 public long getcount(){
 return count;
 }
 private int read() throws IOException{
 return in.read();
 }
 
 
 
 public char readChar() throws IOException{
 int n=read();
 while(isWhiteSpace(n)){
 n=read();
 }
 return (char)n;
 }
 
 public int readInt() throws IOException{
 int number=0;
 int n=read();
 while(isWhiteSpace(n)){
 n=read();
 }
 while(!isWhiteSpace(n)){
 int integer=n-'0';
 number*=10;
 number+=integer;
 n=read();
 }
 return number;
 }
 
 public long readCount() throws IOException{
 long number=0;
 count=0;
 int n=read();
 while(isWhiteSpace(n)){
 n=read();
 }
 while(!isWhiteSpace(n)){
 int integer=n-'0';
 count+=segment[integer];
 number*=10;
 number+=integer;
 n=read();
 }
 return number;
 }
 
 
 public long readLong() throws IOException{
 long number=0;
 int n=read();
 while(isWhiteSpace(n)){
 n=read();
 }
 while(!isWhiteSpace(n)){
 int integer=n-'0';
 number*=10;
 number+=integer;
 n=read();
 }
 return number;
 }
 
 private boolean isWhiteSpace(int n){
 if(n=='\n'||n=='\r'||n=='\t'||n==' '||n==-1){
 return true;
 }else{
 return false;
 }
 
 }
 }