0

I have the following pattern. I want to express 'a' as a function of n.

if n=0 then a=0
if n=1 then a=0
if n=2 then a=3
if n=3 then a=3
if n=4 then a=10
. 
.
.
if n=10 then a=10
if n=11 then a=29
.
.
. 
if n=29 then a=29
if n=30 then a=66
.
.
.
if n=66 then a=66
if n=67 then a=127
.
.

AS you can see the value of a remains the same till a value matches with n. After which the value of a changes and again this value holds till a<=n. I found the formula with which this pattern occurrs. It is

a = 1^3 + 2 when n<=3

a = 2^3 + 2 when n > 3 and n <=10 and so on.

How to express a as a function of n ? like f(n) = {___ <condition>

Maha
  • 41
  • 4
  • what is the value of a for n > 10 ? it is again 1^3 + 2 ? – zenwraight Sep 04 '18 at 21:00
  • @zenwraight for `n > 10` and `n <= 29` `a = 3^3 + 2` ,, `n>29` and `n <= 66` `a=4^3 + 2` – Maha Sep 04 '18 at 21:06
  • "AS you can see the value of a remains the same till a value matches with n" contradicts to first four examples for n and a you give. Or did I miss something ? – rocksportrocker Sep 04 '18 at 21:15
  • Why does the sequence start with 0 instead of 2? – m69's been on strike for years Sep 04 '18 at 21:17
  • @rocksportrocker Yes it contradicts for n=0 and n=1. So i am assuming those are base cases. The pattern starts from n = 2. a=1^3 + 2. so a = 3. when n=3, a=3. when n=4, a=2^3+2=10.Then for n=4,5,6,7,8,9,10, the a=10. When n=11, a=3^3+2=29. Then for n=11 till 29 the a=29 – Maha Sep 04 '18 at 21:24
  • Seems like `a` is the value in the sequence `[1^3+2, 2^3+2, 3^3+2, ..., i^3+2, ...]` that is greater than or equal to `n`. I would do a binary search in this sequence bound by `1 <= i <= n` and you'd get your result in `O(log n)` time – Amit Sep 04 '18 at 21:35
  • @Amit Thank you for the answer. But i want to express it as a function. For example, if n=1 then a=1,if n=2 then a=2, `f(n)={n where n=a`. I want to write in this format. – Maha Sep 04 '18 at 21:40
  • when n is 128 a=218=6^3+2. a value will be same till n=218. when n = 219, a = 7^3+2 = 345. when n=346, a = 8^3 + 2 and so on... – Maha Sep 04 '18 at 21:53
  • a = (ceil((n-2)^1/3))^3+2 (where ceil means "ceiling", or "round up"); the values for n=0 and 1 will have to be hard-coded. – m69's been on strike for years Sep 04 '18 at 21:56
  • @m69 This doesnt work. when n=9 and 10, I am getting a = 29. It is supposed to be 10 for n=9 and 10 – Maha Sep 04 '18 at 22:06
  • In the future if you ever come across another series you need a formula for wolfram alpha is a great tool to use to find one – Mitch Sep 04 '18 at 22:54

1 Answers1

3

You can apply the inverse of the formula n^3-2, round up, and then apply the formula again, to get the correct sequence. The values for 0, 1 and 2 have to be hard-coded, though.

Note: in languages with typed numbers, make sure the result of the cubic root is a float; if it is converted to int automatically, it will be rounded down in the conversion. 

function calculate(n) {
    if (n <= 1) return 0;
    if (n == 2) return 3;
    return Math.pow(Math.ceil(Math.pow(n - 2, 1 / 3)), 3) + 2;
}

for (var i = 0; i < 70; i++) {
    document.write(i + "&rarr;" + calculate(i) + " ; ");
}

Addendum: as Stefan Mondelaers commented, you have to be careful when relying on floating point maths. The code above makes use of the fact that cubic roots of third powers are always slightly underestimated in JavaScript (at least in all current browsers I tested); e.g. the largest third power within JavaScript's safe integer range is 4,503,569,204,744,000 but instead of its cubic root 165,140 you will get: 

document.write(Math.pow(4503569204744000, 1/3));

If you're going to round off the results of floating point calculations, these very small errors may lead to bigger errors. The simplest work-around is indeed to add or subtract a very small value before rounding. For more information see e.g. this question.

m69's been on strike for years
  • 11,835
  • 3
  • 34
  • 57
  • Amazing ! Thank you so much ! – Maha Sep 04 '18 at 22:38
  • Looks good but the Math.ceil fuction is a discrete function and might cause unexpected results for some values because of rounding errors in the floating point calculation of its argument. Even with a high precision floating point, the smallest possible rounding error because of the limited precision of the floating point can have effect on the Math.ceil method if the argument would be an integer if exactly calculated. To solve that problem, I would subtract a very small number from the result of Math.pow before applying Math.ceil. – Stefan Mondelaers Sep 21 '18 at 12:30
  • @StefanMondelaers In JavaScript this is safe, because `Math.pow(Math.pow(n,3),1/3)` is consistently less than or equal to n, but you're right that you can't really count on that to always be true. I'll add a note to the answer. – m69's been on strike for years Sep 21 '18 at 23:31