nacci

Generate numbers in a k-bonacci sequence (where each term is the sum of the previous k terms) with customizable k, initial terms, strategies and data types (number, bigint, etc).

Features

• Convenience: Quickly create sequences of Fibonacci, Tribonacci and beyond.

• K-bonacci: Generate k-bonacci sequences for any k >= 2. If you've ever wanted to create a Dodecanacci (k = 12) or Hectonacci (k = 100), now you can!

• Custom Terms: Sequences can be created with custom initial terms.

• Negative Indices: Sequences extend in both the positive and negative direction. Generate the -100th term just as easily as the 100th.

• Data-Type Agnostic: Whether you need sequences with standard numbers, BigInts, or a custom type, Nacci has you covered. Any type can be used as long as type operations are provided (See NumericOps).

• Performance: Go beyond traditional generation methods with advanced strategies. These offer improved time and space performance for efficient access to deeper indices.

Install

Using npm:

npm install nacci

Using yarn:

yarn install nacci

Usage

Here are some examples for getting started. To experiment, try (JSFiddle).

Fibonacci

Create a standard Fibonacci sequence

const { Fibonacci } = require("nacci");

const fib = new Fibonacci();

// Get the 10th term
console.log(fib.get(10));
// = 55

BigFibonacci

Create a Fibonacci sequence with bigints

const { BigFibonacci } = require("nacci");

const bigFib = new BigFibonacci();

// Get the 256th term
console.log(bigFib.get(256n));
// = 141,693,817,714,056,513,234,709,965,875,411,919,657,707,794,958,199,867n

Negative terms

const { Fibonacci } = require("nacci");

const fib = new Fibonacci();

// Get the -10th term
console.log(fib.get(-10));
// = -55

Custom initial terms

Create the Lucas numbers

const { Fibonacci } = require("nacci");

const lucas = new Fibonacci([2, 1]);

// Get the 10th term
console.log(lucas.get(10));
// = 123

K-bonacci

Create a k-bonacci sequence with a given k

const { Kbonacci } = require("nacci");

// Initialize a pentanacci sequence (K = 5)
const penta = new Kbonacci(5);

// Get the 10th term
console.log(penta.get(10));
// = 236

Create another sequence, this time with bigints and custom initial terms.

const { BigKbonacci } = require("nacci");

const bigPenta = new BigKbonacci(5, [2n, 3n, 5n, 7n, 11n]);

// Get the 128th term
console.log(bigPenta.get(128n));
// = 34,793,317,941,356,809,321,160,944,117,101,129,141n

Caching

Caching is enabled by default to potentially improve subsequent calls. This can be turned on or off.

const { Tribonacci } = require("nacci");

// Create with caching off
const customs = [1, 2, 3];
const seq = new Tribonacci(customs, false);

// Turn on caching
seq.setCached(true);

Advanced Usage

For more control over your sequences. Available options are:

• Generation strategies
• Encoding strategies
• Data type operations

Custom Dodecanacci

const nacci = require("nacci");

// Set K for a dodecanacci
const K = 12;

// Use numbers for indices
const indexOps = new nacci.ops.SafeNumOps();

// Use bigints for values
const valueOps = new nacci.ops.BigOps();

// Create the encoding
const encoding = new nacci.enc.RevSumEncoding(valueOps);

// Create the strategy
const seq = new nacci.gen.PowerGen(2, {
  encoding,
  indexOps,
  valueOps,
});

// Get the 128th term.
// The input is a number and
// the output will be a bigint
console.log(seq.get(128));
// = 83,872,747,739,176,371,407,337,180,779,802,816,512n

FAQ

Q: What is the range for K?

2 <= K

There is no fixed upper bound for K.

However, it is limited by 2 main factors. If large Ks are needed, it's advised to thoroughly test your use case.

1. K is a number type, so it is able to safely represent up to 2^53 - 1 (~9.01 quadrillion); aka Number.MAX_SAFE_INTEGER.

2. Available Memory

   Encoding and generation strategies may need to store information whose size scales with K. For example, MatrixEncoding creates KxK matrices, while SumEncoding uses arrays of length K. Since the maximum value for an array's length is 2^32-1 (~4.29 billion), K is lowered to this limit.

   Depending on the environment, the amount of available memory for this information may lower K even further. For example, a quick test on my local machine encountered fatal errors ("JavaScript heap out of memory") at K = 43,450,368. The test ran with Node.js, heap size of ~2GB, and used Kbonacci.

Q: What is the range for indices?

There are no fixed limits for indices.

However, they are limited by 3 main factors. If large (based on distance from 0) indices are needed, it's advised to thoroughly test your use case.

1. The index data type

   For example, if using SafeNumOps, the range is Number.MIN_SAFE_INTEGER <= I <= Number.MAX_SAFE_INTEGER. If using BigOps, the range is based on BigInt's minimum and maximum values (yes, BigInt has limits! If reached, you can expect to encounter "RangeError: Maximum BigInt size exceeded").

2. The value data type

   Similar to above, the generated value should also be representable. This is especially true for values as they grow quickly. For example, the Fibonacci value for index 2^30 is 224,398,770 digits long and over 224MB as a string.

3. Available memory

   Encoding and generation strategies may need to store many instances of the value's data type. For example, MatrixEncoding creates KxK matrices, while SumEncoding uses arrays of length K. Depending on the environment, the amount of available memory may be exhausted, especially for deeper indices where the size of values grows quickly.

Q: What can I use this for?

Use cases include:

1. Computer Algorithms: Can be used in dynamic programming algorithms to solve specific types of problems, such as counting ways of tiling, different paths in a grid, or ways of partitioning objects.

2. Algorithm Analysis: Can be used to analyze the time complexity of algorithms, especially recursive algorithms. The sequence can represent the number of operations or recursive calls being made.

3. Cryptography: Sequences with good pseudo-random properties, such as k-bonacci sequences, can be used in cryptographic algorithms and for generating keys.

4. Modeling: The Fibonacci sequence is well-known for appearing in natural phenomena, such as the branching of trees, the arrangement of leaves on a stem, or the fruit sprouts of a pineapple. For this and more, k-bonacci sequences can be used to model complex natural growth patterns.

5. Financial Markets: Some traders and analysts use the Fibonacci sequence to predict stock market movements. k-bonacci sequences could potentially be applied in similar financial models to predict market dynamics.

6. Queue Theory: In computing and mathematics, k-bonacci sequences can be applied to problems in queue theory where arrival or service follow a pattern similar to these sequences.

7. Graph Theory: Can be used to calculate the number of paths between nodes in certain types of networks.

8. Network Design: Can be utilized in the design and analysis of network topologies, especially in distributed systems where redundancy and fault tolerance are important.

9. Physics and Chemistry: These sequences can model systems where each state is a sum of the previous states, such as in certain types of chain reactions or particle interactions.

10. Biological Systems: The study of population dynamics in biology, where the population at a certain generation can depend on several previous generations, might also find k-bonacci sequences useful for modeling.

License

Copyright (C) 2023-2024 Michael Rojas [e-mail]

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

https://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

---

Made with ❤️ by Michael Rojas