General expression of finite, integer sequence, containing the ceiling function
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I have limited familiarity with sequences in general, so please bear with me.
During an algorithmic problem I encountered the following sequence, which is currently not listed in OEIS.
Describing it in a loosely way:
- for all integers $i$ from 1 up to N compute $a_i=lceil fracNi rceil$. Keep $a_1$ as the first element of the sequence.
- if $a_i+1=lceil fracNi+1 rceil neq a_i$, then keep $a_i+1$ as the next element in the sequence
For example, with N=32, the sequence would be: $32,16,11,8,7,6,5,4,3,2,1$
With N=64 : $64,32,22,16,13,11,10,8,7,6,5,4,3,2,1$
We may also observe that if the sequence consists of $m$ elements, then $b_m = lceil fracNb_1 rceil = 1$, $b_m-1 = lceil fracNb_2 rceil$, $b_m-2 = lceil fracNb_3 rceil$, etc.
Any thoughts on its general expression?
A bit of info on the "Why?" : Suppose that you are given a specification of performing N operations and you can distribute these N operations to k machines, each one performing a single operation at a time. The single operation itself, cannot be split. Which numbers of machine parallelism are actually meaningful? If N=8 and you set k=7 machines parallelly, for the N operations to be completed it will take the same time as k=4 machines (1 to 7 completed in the first iteration, the 8th in the second VS 1 to 4 in the first iteration, 5 to 8 in the second). You have spent more machine resources, but did not decrease the time that the total of N operations need in order to be executed. However, not only divisors of N are meaningful. For N=8, k=3 is a valid option which results in faster computation over k=2.
sequences-and-series
asked Sep 6 at 2:41
Jim
62
 |Â
show 1 more comment
up vote
1
down vote
favorite
I have limited familiarity with sequences in general, so please bear with me.
During an algorithmic problem I encountered the following sequence, which is currently not listed in OEIS.
Describing it in a loosely way:
- for all integers $i$ from 1 up to N compute $a_i=lceil fracNi rceil$. Keep $a_1$ as the first element of the sequence.
- if $a_i+1=lceil fracNi+1 rceil neq a_i$, then keep $a_i+1$ as the next element in the sequence
For example, with N=32, the sequence would be: $32,16,11,8,7,6,5,4,3,2,1$
With N=64 : $64,32,22,16,13,11,10,8,7,6,5,4,3,2,1$
We may also observe that if the sequence consists of $m$ elements, then $b_m = lceil fracNb_1 rceil = 1$, $b_m-1 = lceil fracNb_2 rceil$, $b_m-2 = lceil fracNb_3 rceil$, etc.
Any thoughts on its general expression?
A bit of info on the "Why?" : Suppose that you are given a specification of performing N operations and you can distribute these N operations to k machines, each one performing a single operation at a time. The single operation itself, cannot be split. Which numbers of machine parallelism are actually meaningful? If N=8 and you set k=7 machines parallelly, for the N operations to be completed it will take the same time as k=4 machines (1 to 7 completed in the first iteration, the 8th in the second VS 1 to 4 in the first iteration, 5 to 8 in the second). You have spent more machine resources, but did not decrease the time that the total of N operations need in order to be executed. However, not only divisors of N are meaningful. For N=8, k=3 is a valid option which results in faster computation over k=2.
sequences-and-series
asked Sep 6 at 2:41
Jim
62
Your description of the sequence is too loose. If I start with $N=32$ and all integers $i$ from 1 to 32, then the first term is $a_1=lceil frac 321 rceil = 32$, so how do you get your sequence to go from 1 to 32 (and not from 32 to 1)?
– mathguy
Sep 6 at 2:47
You are right, if we go from 32 downto 1, we will still get the same order of numbers. 1) Does that mean that we can not regard the above as a sequence? 2) Can we find a general expression anyway?
– Jim
Sep 6 at 2:58
Whether there is a closed form or not is a separate question. The closed form is a formula depending on $i$. The way you described the sequence, $a_1$ is always $N$, not $1$. Or do you want to consider the sequence obtained after ordering the results in ascending order? This still doesn't tell you/us whether there will be a closed form, but at least let us help you solve the problem you need to solve, not a different one.
– mathguy
Sep 6 at 3:02
Alright, now I see what I did there. Let me edit this
– Jim
Sep 6 at 3:11
I think I almost understand, given the "bit of info". Things would be much clearer if you rewrote the question to state what you really want - something like "given $N$ equal size jobs to run on $k$ identical machines, which minimal numbers of machines optimize for each given time between $1$ and $N$?" (If that's right.) Then let folks here play with how to provide a good answer. Asking us about the formula is (I think) asking an x-y question. meta.stackexchange.com/questions/66377/what-is-the-xy-problem
– Ethan Bolker
Sep 9 at 17:21
 |Â
show 1 more comment
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I have limited familiarity with sequences in general, so please bear with me.
During an algorithmic problem I encountered the following sequence, which is currently not listed in OEIS.
Describing it in a loosely way:
- for all integers $i$ from 1 up to N compute $a_i=lceil fracNi rceil$. Keep $a_1$ as the first element of the sequence.
- if $a_i+1=lceil fracNi+1 rceil neq a_i$, then keep $a_i+1$ as the next element in the sequence
For example, with N=32, the sequence would be: $32,16,11,8,7,6,5,4,3,2,1$
With N=64 : $64,32,22,16,13,11,10,8,7,6,5,4,3,2,1$
We may also observe that if the sequence consists of $m$ elements, then $b_m = lceil fracNb_1 rceil = 1$, $b_m-1 = lceil fracNb_2 rceil$, $b_m-2 = lceil fracNb_3 rceil$, etc.
Any thoughts on its general expression?
A bit of info on the "Why?" : Suppose that you are given a specification of performing N operations and you can distribute these N operations to k machines, each one performing a single operation at a time. The single operation itself, cannot be split. Which numbers of machine parallelism are actually meaningful? If N=8 and you set k=7 machines parallelly, for the N operations to be completed it will take the same time as k=4 machines (1 to 7 completed in the first iteration, the 8th in the second VS 1 to 4 in the first iteration, 5 to 8 in the second). You have spent more machine resources, but did not decrease the time that the total of N operations need in order to be executed. However, not only divisors of N are meaningful. For N=8, k=3 is a valid option which results in faster computation over k=2.
sequences-and-series
asked Sep 6 at 2:41
Jim
62
I have limited familiarity with sequences in general, so please bear with me.
During an algorithmic problem I encountered the following sequence, which is currently not listed in OEIS.
Describing it in a loosely way:
- for all integers $i$ from 1 up to N compute $a_i=lceil fracNi rceil$. Keep $a_1$ as the first element of the sequence.
- if $a_i+1=lceil fracNi+1 rceil neq a_i$, then keep $a_i+1$ as the next element in the sequence
For example, with N=32, the sequence would be: $32,16,11,8,7,6,5,4,3,2,1$
With N=64 : $64,32,22,16,13,11,10,8,7,6,5,4,3,2,1$
We may also observe that if the sequence consists of $m$ elements, then $b_m = lceil fracNb_1 rceil = 1$, $b_m-1 = lceil fracNb_2 rceil$, $b_m-2 = lceil fracNb_3 rceil$, etc.
Any thoughts on its general expression?
A bit of info on the "Why?" : Suppose that you are given a specification of performing N operations and you can distribute these N operations to k machines, each one performing a single operation at a time. The single operation itself, cannot be split. Which numbers of machine parallelism are actually meaningful? If N=8 and you set k=7 machines parallelly, for the N operations to be completed it will take the same time as k=4 machines (1 to 7 completed in the first iteration, the 8th in the second VS 1 to 4 in the first iteration, 5 to 8 in the second). You have spent more machine resources, but did not decrease the time that the total of N operations need in order to be executed. However, not only divisors of N are meaningful. For N=8, k=3 is a valid option which results in faster computation over k=2.
sequences-and-series
sequences-and-series
asked Sep 6 at 2:41
Jim
62
asked Sep 6 at 2:41
Jim
62
edited Sep 9 at 17:09
asked Sep 6 at 2:41
Jim
62
asked Sep 6 at 2:41
Jim
62
asked Sep 6 at 2:41
Jim
62
62
Your description of the sequence is too loose. If I start with $N=32$ and all integers $i$ from 1 to 32, then the first term is $a_1=lceil frac 321 rceil = 32$, so how do you get your sequence to go from 1 to 32 (and not from 32 to 1)?
– mathguy
Sep 6 at 2:47
You are right, if we go from 32 downto 1, we will still get the same order of numbers. 1) Does that mean that we can not regard the above as a sequence? 2) Can we find a general expression anyway?
– Jim
Sep 6 at 2:58
Whether there is a closed form or not is a separate question. The closed form is a formula depending on $i$. The way you described the sequence, $a_1$ is always $N$, not $1$. Or do you want to consider the sequence obtained after ordering the results in ascending order? This still doesn't tell you/us whether there will be a closed form, but at least let us help you solve the problem you need to solve, not a different one.
– mathguy
Sep 6 at 3:02
Alright, now I see what I did there. Let me edit this
– Jim
Sep 6 at 3:11
I think I almost understand, given the "bit of info". Things would be much clearer if you rewrote the question to state what you really want - something like "given $N$ equal size jobs to run on $k$ identical machines, which minimal numbers of machines optimize for each given time between $1$ and $N$?" (If that's right.) Then let folks here play with how to provide a good answer. Asking us about the formula is (I think) asking an x-y question. meta.stackexchange.com/questions/66377/what-is-the-xy-problem
– Ethan Bolker
Sep 9 at 17:21
 |Â
show 1 more comment
Your description of the sequence is too loose. If I start with $N=32$ and all integers $i$ from 1 to 32, then the first term is $a_1=lceil frac 321 rceil = 32$, so how do you get your sequence to go from 1 to 32 (and not from 32 to 1)?
– mathguy
Sep 6 at 2:47
You are right, if we go from 32 downto 1, we will still get the same order of numbers. 1) Does that mean that we can not regard the above as a sequence? 2) Can we find a general expression anyway?
– Jim
Sep 6 at 2:58
Whether there is a closed form or not is a separate question. The closed form is a formula depending on $i$. The way you described the sequence, $a_1$ is always $N$, not $1$. Or do you want to consider the sequence obtained after ordering the results in ascending order? This still doesn't tell you/us whether there will be a closed form, but at least let us help you solve the problem you need to solve, not a different one.
– mathguy
Sep 6 at 3:02
Alright, now I see what I did there. Let me edit this
– Jim
Sep 6 at 3:11
I think I almost understand, given the "bit of info". Things would be much clearer if you rewrote the question to state what you really want - something like "given $N$ equal size jobs to run on $k$ identical machines, which minimal numbers of machines optimize for each given time between $1$ and $N$?" (If that's right.) Then let folks here play with how to provide a good answer. Asking us about the formula is (I think) asking an x-y question. meta.stackexchange.com/questions/66377/what-is-the-xy-problem
– Ethan Bolker
Sep 9 at 17:21
Your description of the sequence is too loose. If I start with $N=32$ and all integers $i$ from 1 to 32, then the first term is $a_1=lceil frac 321 rceil = 32$, so how do you get your sequence to go from 1 to 32 (and not from 32 to 1)?
– mathguy
Sep 6 at 2:47
Your description of the sequence is too loose. If I start with $N=32$ and all integers $i$ from 1 to 32, then the first term is $a_1=lceil frac 321 rceil = 32$, so how do you get your sequence to go from 1 to 32 (and not from 32 to 1)?
– mathguy
Sep 6 at 2:47
You are right, if we go from 32 downto 1, we will still get the same order of numbers. 1) Does that mean that we can not regard the above as a sequence? 2) Can we find a general expression anyway?
– Jim
Sep 6 at 2:58
You are right, if we go from 32 downto 1, we will still get the same order of numbers. 1) Does that mean that we can not regard the above as a sequence? 2) Can we find a general expression anyway?
– Jim
Sep 6 at 2:58
Whether there is a closed form or not is a separate question. The closed form is a formula depending on $i$. The way you described the sequence, $a_1$ is always $N$, not $1$. Or do you want to consider the sequence obtained after ordering the results in ascending order? This still doesn't tell you/us whether there will be a closed form, but at least let us help you solve the problem you need to solve, not a different one.
– mathguy
Sep 6 at 3:02
Whether there is a closed form or not is a separate question. The closed form is a formula depending on $i$. The way you described the sequence, $a_1$ is always $N$, not $1$. Or do you want to consider the sequence obtained after ordering the results in ascending order? This still doesn't tell you/us whether there will be a closed form, but at least let us help you solve the problem you need to solve, not a different one.
– mathguy
Sep 6 at 3:02
Alright, now I see what I did there. Let me edit this
– Jim
Sep 6 at 3:11
Alright, now I see what I did there. Let me edit this
– Jim
Sep 6 at 3:11
I think I almost understand, given the "bit of info". Things would be much clearer if you rewrote the question to state what you really want - something like "given $N$ equal size jobs to run on $k$ identical machines, which minimal numbers of machines optimize for each given time between $1$ and $N$?" (If that's right.) Then let folks here play with how to provide a good answer. Asking us about the formula is (I think) asking an x-y question. meta.stackexchange.com/questions/66377/what-is-the-xy-problem
– Ethan Bolker
Sep 9 at 17:21
I think I almost understand, given the "bit of info". Things would be much clearer if you rewrote the question to state what you really want - something like "given $N$ equal size jobs to run on $k$ identical machines, which minimal numbers of machines optimize for each given time between $1$ and $N$?" (If that's right.) Then let folks here play with how to provide a good answer. Asking us about the formula is (I think) asking an x-y question. meta.stackexchange.com/questions/66377/what-is-the-xy-problem
– Ethan Bolker
Sep 9 at 17:21
 |Â
show 1 more comment
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2907026%2fgeneral-expression-of-finite-integer-sequence-containing-the-ceiling-function%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Your description of the sequence is too loose. If I start with $N=32$ and all integers $i$ from 1 to 32, then the first term is $a_1=lceil frac 321 rceil = 32$, so how do you get your sequence to go from 1 to 32 (and not from 32 to 1)?
– mathguy
Sep 6 at 2:47
You are right, if we go from 32 downto 1, we will still get the same order of numbers. 1) Does that mean that we can not regard the above as a sequence? 2) Can we find a general expression anyway?
– Jim
Sep 6 at 2:58
Whether there is a closed form or not is a separate question. The closed form is a formula depending on $i$. The way you described the sequence, $a_1$ is always $N$, not $1$. Or do you want to consider the sequence obtained after ordering the results in ascending order? This still doesn't tell you/us whether there will be a closed form, but at least let us help you solve the problem you need to solve, not a different one.
– mathguy
Sep 6 at 3:02
Alright, now I see what I did there. Let me edit this
– Jim
Sep 6 at 3:11
I think I almost understand, given the "bit of info". Things would be much clearer if you rewrote the question to state what you really want - something like "given $N$ equal size jobs to run on $k$ identical machines, which minimal numbers of machines optimize for each given time between $1$ and $N$?" (If that's right.) Then let folks here play with how to provide a good answer. Asking us about the formula is (I think) asking an x-y question. meta.stackexchange.com/questions/66377/what-is-the-xy-problem
– Ethan Bolker
Sep 9 at 17:21