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 '.
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:
2 use m=2 where A = 0,1
2,3 use m=2×3 where A = 0,1,0,0,0,1
2,3,5 use m=2×3×5 where A = 0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1
2,3,5,7 use m=2×3×5×7 where A =
0,1,0,0,0,0,0,0,0,0, 0,1,0,1,0,0,0,1,0,1, 0,0,0,1,0,0,0,0,0,1, 0,1,0,0,0,0,0,1,0,0, 0,1,0,1,0,0,0,1,0,0, 0,0,0,1,0,0,0,0,0,1, 0,1,0,0,0,0,0,1,0,0, 0,1,0,1,0,0,0,0,0,1, 0,0,0,1,0,0,0,0,0,1, 0,0,0,0,0,0,0,1,0,0, 0,1,0,1,0,0,0,1,0,1, 0,0,0,1,0,0,0,0,0,0, 0,1,0,0,0,0,0,1,0,0, 0,1,0,0,0,0,0,1,0,1, 0,0,0,1,0,0,0,0,0,1, 0,1,0,0,0,0,0,1,0,0, 0,0,0,1,0,0,0,1,0,1, 0,0,0,1,0,0,0,0,0,1, 0,1,0,0,0,0,0,1,0,0, 0,1,0,1,0,0,0,1,0,1, 0,0,0,0,0,0,0,0,0,1
2,3,5,7,... use m=2×3×5×7×... where A = ...
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
(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 := LHS+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));
