Math FullFloor function

The fullfloor function is a new math function that finds the nth element of a non-decreasing sequence of integers having a repetitive pattern. An example of such a sequence is {0,0,1,2,2,2, 3,3,4,5,5,5, 6,6,7,8,8,8, ...}. It can be used to generate sequences of the form 'not a multiple of '.

Contents:

  1. Definition
  2. Implementation
  3. Not-a-multiple-of
  4. Links

Definition

The function is defined as:



where A is the array containing the needed information about the sequence: Ak is the number of times k will appear successively, counting from k=0. m = length(A) = number of elements in A. sum(A) = sum of elements in A. ⌊a/b⌋ is the signed integer division of a by b, which corresponds to ⌊x⌋ = floor(x) = largest integer smaller than or equal to x.

For the sequence {0,0,1,2,2,2, ...} the array A = (2,1,3). This is because 0 appears two times, 1 appears one time and 2 appears three times. The sequence then extends in a repetitive pattern both to the left (values less than 0) and to the right (values greater than 2). Given A, m=3 and sum(A)=6, the equation becomes:



Notice that when m=1 the fullfloor function is exactly the same as the floor function. The fullfloor function can be implemented to run in O(m) time complexity, by updating the value of the numerator on each iteration of i. This function was created through the analysis of the sequence which it generates. It can be proven in the same way it was created.


Implementation

Generate for n from to
Array A =
Offset result by




To generate all integers not multiples of:

Below is the implemented JavaScript code.
function get_output_sequence()
{
    var fr, to, A=[], offset, t=[0];

    // obtain the input strings
    var s1 = document.getElementById("n_fr").value;
    var s2 = document.getElementById("n_to").value;
    var s3 = document.getElementById("array_A").value;
    var s4 = document.getElementById("offset").value;

    // convert to integers
    if(!str_to_int (t, s1)) return; fr = t[0];
    if(!str_to_int (t, s2)) return; to = t[0];
    if(!str_to_int_array (A, s3)) return;
    if(!str_to_int (t, s4)) offset=0; else offset = t[0];

    // prepare for the algorithm
    var m = A.length;
    var sum_of_A = 0;
    for(var i=0; i<m; i++) sum_of_A += A[i];

    var out = [];
    var k = 0;
    for(var n = fr; n <= to; n++) // for each n
    {
        // get y = fullfloor(n,A)
        var numerator = n;
        var y = offset;
        for(var i=1; i<=m; i++)
        {
            y += Math.floor(numerator / sum_of_A);
            numerator += A[m-i];
        }
        out[k++] = y;
    }
    display_message(out.join(", "));
}


Not a multiple of

In an attempt to generate the nth element of sequences that are not multiples of certain numbers, as part of working towards generating prime numbers, the pattern in the sequences was thoroughly analysed and it was observed that the aim can be attained by using the fullfloor function. The following are examples:

Sequence of the form: not a×n for a>0

The nth element not a multiple of a positive integer a is












Copy the RFET script below and evaluate it online.
 (m, a, c, t), y ;

#{
 Given m=7 and a, this RFET script will generate
 the sequence of elements that are not multiples
 of m nor of the a-th element not a multiple of m.

 Note: all operations here are per-value only.
 That is each element of a vector is processed
 independently of any other element.
}#

m = 7;
a = 0 := current+1;   # update 'a' before evaluation

c = g(a);      # c = a-th element not multiple of m

v = vector(0,1,100);  # v is the initial vector
y = g(h(v));          # y is the result vector

s = (y mod c).==0;    # 's' is a vector of 0s and 1s
t = sum(s);           # there should be no 1 in 's'

g(n) = floor(m*n ./ (m-1))+1; # do per-value division

# 'n' can be any value-structure, even a matrix
h(n) = n + fullfloor(n+a, (b1,b3,b4,b2,b4,b3));

b1 = fullfloor(a,(1,0));
b2 = fullfloor(a,(2,0));
b3 = fullfloor(a,(1,1,2,1,1,0));
b4 = fullfloor(a,(1,2,0,2,1,0));
The result of evaluation is:
((7, 1, 2, 0),
 (1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 33, 37, 39, 41, 43, 45, 47, 51, 53, 55, 57, 59, 61, 65, 67, 69, 71, 73, 75, 79, 81, 83, 85, 87, 89, 93, 95, 97, 99, 101, 103, 107, 109, 111, 113, 115, 117, 121, 123, 125, 127, 129, 131, 135, 137, 139, 141, 143, 145, 149, 151, 153, 155, 157, 159, 163, 165, 167, 169, 171, 173, 177, 179, 181, 183, 185, 187, 191, 193, 195, 197, 199, 201, 205, 207, 209, 211, 213, 215, 219, 221, 223, 225, 227, 229, 233))


Links

  1. http://en.wikipedia.org/wiki/Floor_and_ceiling_functions
  2. Algorithms - Generating prime numbers
  3. Generate nth palindromic number
  4. Math expression parsing algorithm
  5. Convert sorted list to complete BST
  6. Find maximum bipartite matching
  7. Applications - Rhyscitlema Calculator