Is it an arithmetico-geometric sequence?
up vote
11
down vote
favorite
An arithmetico-geometric sequence is the elementwise product of an arithmetic sequence and a geometric sequence. For example, 1 -4 12 -32
is the product of the arithmetic sequence 1 2 3 4
and the geometric sequence 1 -2 4 -8
. The nth term of an integer arithmetico-geometric sequence can be expressed as
$$a_n = r^n cdot (a_0 + nd)$$
for some real number $d$, nonzero real $r$, and integer $a_0$. Note that $r$ and $d$ are not necessarily integers.
For example, the sequence 2 11 36 100 256 624 1472 3392
has $a_0 = 2$, $r = 2$, and $d = 3.5$.
Input
An ordered list of $n ge 2$ integers as input in any reasonable format. Since some definitions of geometric sequence allow $r=0$ and define $0^0 = 1$, whether an input is an arithmetico-geometric sequence will not depend on whether $r$ is allowed to be 0. For example, 123 0 0 0 0
will not occur as input.
Output
Whether it is an arithmetico-geometric sequence. Output a truthy/falsy value, or two different consistent values.
Test cases
True:
1 -4 12 -32
0 0 0
-192 0 432 -1296 2916 -5832 10935 -19683
2 11 36 100 256 624 1472 3392
-4374 729 972 567 270 117 48 19
24601 1337 42
0 -2718
-1 -1 0 4 16
2 4 8 16 32 64
2 3 4 5 6 7
0 2 8 24
False:
4 8 15 16 23 42
3 1 4 1
24601 42 1337
0 0 0 1
0 0 1 0 0
1 -1 0 4 16
code-golf math decision-problem
|
show 1 more comment
up vote
11
down vote
favorite
An arithmetico-geometric sequence is the elementwise product of an arithmetic sequence and a geometric sequence. For example, 1 -4 12 -32
is the product of the arithmetic sequence 1 2 3 4
and the geometric sequence 1 -2 4 -8
. The nth term of an integer arithmetico-geometric sequence can be expressed as
$$a_n = r^n cdot (a_0 + nd)$$
for some real number $d$, nonzero real $r$, and integer $a_0$. Note that $r$ and $d$ are not necessarily integers.
For example, the sequence 2 11 36 100 256 624 1472 3392
has $a_0 = 2$, $r = 2$, and $d = 3.5$.
Input
An ordered list of $n ge 2$ integers as input in any reasonable format. Since some definitions of geometric sequence allow $r=0$ and define $0^0 = 1$, whether an input is an arithmetico-geometric sequence will not depend on whether $r$ is allowed to be 0. For example, 123 0 0 0 0
will not occur as input.
Output
Whether it is an arithmetico-geometric sequence. Output a truthy/falsy value, or two different consistent values.
Test cases
True:
1 -4 12 -32
0 0 0
-192 0 432 -1296 2916 -5832 10935 -19683
2 11 36 100 256 624 1472 3392
-4374 729 972 567 270 117 48 19
24601 1337 42
0 -2718
-1 -1 0 4 16
2 4 8 16 32 64
2 3 4 5 6 7
0 2 8 24
False:
4 8 15 16 23 42
3 1 4 1
24601 42 1337
0 0 0 1
0 0 1 0 0
1 -1 0 4 16
code-golf math decision-problem
1
FYI you can use inline math mode with$
to write things like $ a_{0} $.
– FryAmTheEggman
Nov 20 at 2:28
Are two-term inputs indeed possible? There aren't any in the test cases.
– xnor
Nov 20 at 3:40
@xnor Trivially you can set $r=1$ or $d=0$ so the sequences aren't unique in that case, but the output should always be truthy
– Giuseppe
Nov 20 at 3:55
1
Suggest testcase 0 2 8 24, 0 0 1, 0 0 0 1
– tsh
Nov 20 at 12:12
1
1 -1 0 4 16
would be a useful False case, since it shares four consecutive elements with each of the True cases1 -1 0 4 -16
and-1 -1 0 4 16
.
– Anders Kaseorg
Nov 20 at 22:33
|
show 1 more comment
up vote
11
down vote
favorite
up vote
11
down vote
favorite
An arithmetico-geometric sequence is the elementwise product of an arithmetic sequence and a geometric sequence. For example, 1 -4 12 -32
is the product of the arithmetic sequence 1 2 3 4
and the geometric sequence 1 -2 4 -8
. The nth term of an integer arithmetico-geometric sequence can be expressed as
$$a_n = r^n cdot (a_0 + nd)$$
for some real number $d$, nonzero real $r$, and integer $a_0$. Note that $r$ and $d$ are not necessarily integers.
For example, the sequence 2 11 36 100 256 624 1472 3392
has $a_0 = 2$, $r = 2$, and $d = 3.5$.
Input
An ordered list of $n ge 2$ integers as input in any reasonable format. Since some definitions of geometric sequence allow $r=0$ and define $0^0 = 1$, whether an input is an arithmetico-geometric sequence will not depend on whether $r$ is allowed to be 0. For example, 123 0 0 0 0
will not occur as input.
Output
Whether it is an arithmetico-geometric sequence. Output a truthy/falsy value, or two different consistent values.
Test cases
True:
1 -4 12 -32
0 0 0
-192 0 432 -1296 2916 -5832 10935 -19683
2 11 36 100 256 624 1472 3392
-4374 729 972 567 270 117 48 19
24601 1337 42
0 -2718
-1 -1 0 4 16
2 4 8 16 32 64
2 3 4 5 6 7
0 2 8 24
False:
4 8 15 16 23 42
3 1 4 1
24601 42 1337
0 0 0 1
0 0 1 0 0
1 -1 0 4 16
code-golf math decision-problem
An arithmetico-geometric sequence is the elementwise product of an arithmetic sequence and a geometric sequence. For example, 1 -4 12 -32
is the product of the arithmetic sequence 1 2 3 4
and the geometric sequence 1 -2 4 -8
. The nth term of an integer arithmetico-geometric sequence can be expressed as
$$a_n = r^n cdot (a_0 + nd)$$
for some real number $d$, nonzero real $r$, and integer $a_0$. Note that $r$ and $d$ are not necessarily integers.
For example, the sequence 2 11 36 100 256 624 1472 3392
has $a_0 = 2$, $r = 2$, and $d = 3.5$.
Input
An ordered list of $n ge 2$ integers as input in any reasonable format. Since some definitions of geometric sequence allow $r=0$ and define $0^0 = 1$, whether an input is an arithmetico-geometric sequence will not depend on whether $r$ is allowed to be 0. For example, 123 0 0 0 0
will not occur as input.
Output
Whether it is an arithmetico-geometric sequence. Output a truthy/falsy value, or two different consistent values.
Test cases
True:
1 -4 12 -32
0 0 0
-192 0 432 -1296 2916 -5832 10935 -19683
2 11 36 100 256 624 1472 3392
-4374 729 972 567 270 117 48 19
24601 1337 42
0 -2718
-1 -1 0 4 16
2 4 8 16 32 64
2 3 4 5 6 7
0 2 8 24
False:
4 8 15 16 23 42
3 1 4 1
24601 42 1337
0 0 0 1
0 0 1 0 0
1 -1 0 4 16
code-golf math decision-problem
code-golf math decision-problem
edited Nov 21 at 3:51
asked Nov 20 at 2:11
lirtosiast
15.6k436107
15.6k436107
1
FYI you can use inline math mode with$
to write things like $ a_{0} $.
– FryAmTheEggman
Nov 20 at 2:28
Are two-term inputs indeed possible? There aren't any in the test cases.
– xnor
Nov 20 at 3:40
@xnor Trivially you can set $r=1$ or $d=0$ so the sequences aren't unique in that case, but the output should always be truthy
– Giuseppe
Nov 20 at 3:55
1
Suggest testcase 0 2 8 24, 0 0 1, 0 0 0 1
– tsh
Nov 20 at 12:12
1
1 -1 0 4 16
would be a useful False case, since it shares four consecutive elements with each of the True cases1 -1 0 4 -16
and-1 -1 0 4 16
.
– Anders Kaseorg
Nov 20 at 22:33
|
show 1 more comment
1
FYI you can use inline math mode with$
to write things like $ a_{0} $.
– FryAmTheEggman
Nov 20 at 2:28
Are two-term inputs indeed possible? There aren't any in the test cases.
– xnor
Nov 20 at 3:40
@xnor Trivially you can set $r=1$ or $d=0$ so the sequences aren't unique in that case, but the output should always be truthy
– Giuseppe
Nov 20 at 3:55
1
Suggest testcase 0 2 8 24, 0 0 1, 0 0 0 1
– tsh
Nov 20 at 12:12
1
1 -1 0 4 16
would be a useful False case, since it shares four consecutive elements with each of the True cases1 -1 0 4 -16
and-1 -1 0 4 16
.
– Anders Kaseorg
Nov 20 at 22:33
1
1
FYI you can use inline math mode with
$
to write things like $ a_{0} $.– FryAmTheEggman
Nov 20 at 2:28
FYI you can use inline math mode with
$
to write things like $ a_{0} $.– FryAmTheEggman
Nov 20 at 2:28
Are two-term inputs indeed possible? There aren't any in the test cases.
– xnor
Nov 20 at 3:40
Are two-term inputs indeed possible? There aren't any in the test cases.
– xnor
Nov 20 at 3:40
@xnor Trivially you can set $r=1$ or $d=0$ so the sequences aren't unique in that case, but the output should always be truthy
– Giuseppe
Nov 20 at 3:55
@xnor Trivially you can set $r=1$ or $d=0$ so the sequences aren't unique in that case, but the output should always be truthy
– Giuseppe
Nov 20 at 3:55
1
1
Suggest testcase 0 2 8 24, 0 0 1, 0 0 0 1
– tsh
Nov 20 at 12:12
Suggest testcase 0 2 8 24, 0 0 1, 0 0 0 1
– tsh
Nov 20 at 12:12
1
1
1 -1 0 4 16
would be a useful False case, since it shares four consecutive elements with each of the True cases 1 -1 0 4 -16
and -1 -1 0 4 16
.– Anders Kaseorg
Nov 20 at 22:33
1 -1 0 4 16
would be a useful False case, since it shares four consecutive elements with each of the True cases 1 -1 0 4 -16
and -1 -1 0 4 16
.– Anders Kaseorg
Nov 20 at 22:33
|
show 1 more comment
3 Answers
3
active
oldest
votes
up vote
2
down vote
Perl 6, 184 128 135 bytes
{3>$_||->x,y,z{?grep ->r{min (x,{r&&r*$_+(y/r -x)*($×=r)}...*)Z==$_},x??map (y+*×sqrt(y²-x*z).narrow)/x,1,-1!!y&&z/y/2}(|.[^3])}
Try it online!
Computes $r$ and $d$ from the first three elements and checks whether the resulting sequence matches the input. Unfortunately, Rakudo throws an exception when dividing by zero, even when using floating-point numbers, costing ~9 bytes.
Enumerates the sequence using $a_n=r cdot a_{n-1}+r^n cdot d$.
Some improvements are inspired by Arnauld's JavaScript answer.
Explanation
3>$_|| # Return true if there are less than three elements
->x,y,z{ ... }(|.[^3])} # Bind x,y,z to first three elements
# Candidates for r
x # If x != 0
??map (y+*×sqrt(y²-x*z).narrow)/x,1,-1 # then solutions of quadratic equation
!!y&&z/y/2 # else solution of linear equation or 0 if y==0
?grep ->r{ ... }, # Is there an r for which the following is true?
( , ...*) # Create infinite sequence
x # Start with x
{ } # Compute next term
r&& # 0 if r==0
(y/r -x) # d
r*$_ # r*a(n-1)
($×=r) # r^n
+ * # r*a(n-1)+d*r^n
Z==$_ # Compare with each element of input
min # All elements are equal?
add a comment |
up vote
2
down vote
JavaScript (ES7), 135 127 bytes
a=>!([x,y,z]=a,1/z)|!a.some(n=>n)|[y/x+(d=(y*y-x*z)**.5/x),y/x-d,z/y/2].some(r=>a.every((v,n)=>(v-(x+n*y/r-n*x)*r**n)**2<1e-9))
Try it online!
How?
We use two preliminary tests to get rid of some special cases. For the main case, we try three different possible values of $r$ (and the corresponding values of $d$, which can be easily deduced) and test whether all terms of the input sequence are matching the guessed ones. Because of potential rounding errors, we actually test whether all squared differences are $<10^{-9}$.
Special case #1: less than 3 terms
If there are less than 3 terms, it's always possible to find a matching sequence. So we force a truthy value.
Special case #2: only zeros
If all terms are equal to $0$, we can use $a_0=0$, $d=0$ and any $rneq 0$. So we force a truthy value.
Main case with $a_0=0$
If $a_0=0$, the sequence can be simplified to:
$$a_n=r^ntimes ntimes d$$
Which gives:
$$a_1=rtimes d\
a_2=2r^2times d$$
We know that $d$ is not equal to $0$ (otherwise, we'd be in the special case #2). So we have $a_1neq 0$ and:
$$r=frac{a_2}{2a_1}$$
Main case with $a_0neq 0$
We have the following relation between $a_{n+1}$ and $a_n$:
$$a_{n+1}=r.a_n+r^{n+1}d$$
For $a_{n+2}$, we have:
$$begin{align}a_{n+2}&=r.a_{n+1}+r^{n+2}d\
&=r(r.a_n+r^{n+1}d)+r^{n+2}d\
&=r^2a_n+2r.r^{n+1}d\
&=r^2a_n+2r(a_{n+1}-r.a_n)\
&=-r^2a_n+2r.a_{n+1}
end{align}$$
We notably have:
$$a_2=-r^2a_0+2r.a_1$$
Leading to the following quadratic:
$$r^2a_0-2r.a_1+a_2=0$$
Whose roots are:
$$r_0=frac{a_1+sqrt{{a_1}^2-a_0a_2}}{a_0}\
r_1=frac{a_1-sqrt{{a_1}^2-a_0a_2}}{a_0}$$
add a comment |
up vote
2
down vote
Wolfram Language (Mathematica), 55 bytes
{}!=Solve[i=Range@Tr[1^#];(a+i*d)r^i==#,{r,a,d},Reals]&
Try it online!
Solve
return all solution forms. The result is compared with {}
to check if there is any solution.
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Perl 6, 184 128 135 bytes
{3>$_||->x,y,z{?grep ->r{min (x,{r&&r*$_+(y/r -x)*($×=r)}...*)Z==$_},x??map (y+*×sqrt(y²-x*z).narrow)/x,1,-1!!y&&z/y/2}(|.[^3])}
Try it online!
Computes $r$ and $d$ from the first three elements and checks whether the resulting sequence matches the input. Unfortunately, Rakudo throws an exception when dividing by zero, even when using floating-point numbers, costing ~9 bytes.
Enumerates the sequence using $a_n=r cdot a_{n-1}+r^n cdot d$.
Some improvements are inspired by Arnauld's JavaScript answer.
Explanation
3>$_|| # Return true if there are less than three elements
->x,y,z{ ... }(|.[^3])} # Bind x,y,z to first three elements
# Candidates for r
x # If x != 0
??map (y+*×sqrt(y²-x*z).narrow)/x,1,-1 # then solutions of quadratic equation
!!y&&z/y/2 # else solution of linear equation or 0 if y==0
?grep ->r{ ... }, # Is there an r for which the following is true?
( , ...*) # Create infinite sequence
x # Start with x
{ } # Compute next term
r&& # 0 if r==0
(y/r -x) # d
r*$_ # r*a(n-1)
($×=r) # r^n
+ * # r*a(n-1)+d*r^n
Z==$_ # Compare with each element of input
min # All elements are equal?
add a comment |
up vote
2
down vote
Perl 6, 184 128 135 bytes
{3>$_||->x,y,z{?grep ->r{min (x,{r&&r*$_+(y/r -x)*($×=r)}...*)Z==$_},x??map (y+*×sqrt(y²-x*z).narrow)/x,1,-1!!y&&z/y/2}(|.[^3])}
Try it online!
Computes $r$ and $d$ from the first three elements and checks whether the resulting sequence matches the input. Unfortunately, Rakudo throws an exception when dividing by zero, even when using floating-point numbers, costing ~9 bytes.
Enumerates the sequence using $a_n=r cdot a_{n-1}+r^n cdot d$.
Some improvements are inspired by Arnauld's JavaScript answer.
Explanation
3>$_|| # Return true if there are less than three elements
->x,y,z{ ... }(|.[^3])} # Bind x,y,z to first three elements
# Candidates for r
x # If x != 0
??map (y+*×sqrt(y²-x*z).narrow)/x,1,-1 # then solutions of quadratic equation
!!y&&z/y/2 # else solution of linear equation or 0 if y==0
?grep ->r{ ... }, # Is there an r for which the following is true?
( , ...*) # Create infinite sequence
x # Start with x
{ } # Compute next term
r&& # 0 if r==0
(y/r -x) # d
r*$_ # r*a(n-1)
($×=r) # r^n
+ * # r*a(n-1)+d*r^n
Z==$_ # Compare with each element of input
min # All elements are equal?
add a comment |
up vote
2
down vote
up vote
2
down vote
Perl 6, 184 128 135 bytes
{3>$_||->x,y,z{?grep ->r{min (x,{r&&r*$_+(y/r -x)*($×=r)}...*)Z==$_},x??map (y+*×sqrt(y²-x*z).narrow)/x,1,-1!!y&&z/y/2}(|.[^3])}
Try it online!
Computes $r$ and $d$ from the first three elements and checks whether the resulting sequence matches the input. Unfortunately, Rakudo throws an exception when dividing by zero, even when using floating-point numbers, costing ~9 bytes.
Enumerates the sequence using $a_n=r cdot a_{n-1}+r^n cdot d$.
Some improvements are inspired by Arnauld's JavaScript answer.
Explanation
3>$_|| # Return true if there are less than three elements
->x,y,z{ ... }(|.[^3])} # Bind x,y,z to first three elements
# Candidates for r
x # If x != 0
??map (y+*×sqrt(y²-x*z).narrow)/x,1,-1 # then solutions of quadratic equation
!!y&&z/y/2 # else solution of linear equation or 0 if y==0
?grep ->r{ ... }, # Is there an r for which the following is true?
( , ...*) # Create infinite sequence
x # Start with x
{ } # Compute next term
r&& # 0 if r==0
(y/r -x) # d
r*$_ # r*a(n-1)
($×=r) # r^n
+ * # r*a(n-1)+d*r^n
Z==$_ # Compare with each element of input
min # All elements are equal?
Perl 6, 184 128 135 bytes
{3>$_||->x,y,z{?grep ->r{min (x,{r&&r*$_+(y/r -x)*($×=r)}...*)Z==$_},x??map (y+*×sqrt(y²-x*z).narrow)/x,1,-1!!y&&z/y/2}(|.[^3])}
Try it online!
Computes $r$ and $d$ from the first three elements and checks whether the resulting sequence matches the input. Unfortunately, Rakudo throws an exception when dividing by zero, even when using floating-point numbers, costing ~9 bytes.
Enumerates the sequence using $a_n=r cdot a_{n-1}+r^n cdot d$.
Some improvements are inspired by Arnauld's JavaScript answer.
Explanation
3>$_|| # Return true if there are less than three elements
->x,y,z{ ... }(|.[^3])} # Bind x,y,z to first three elements
# Candidates for r
x # If x != 0
??map (y+*×sqrt(y²-x*z).narrow)/x,1,-1 # then solutions of quadratic equation
!!y&&z/y/2 # else solution of linear equation or 0 if y==0
?grep ->r{ ... }, # Is there an r for which the following is true?
( , ...*) # Create infinite sequence
x # Start with x
{ } # Compute next term
r&& # 0 if r==0
(y/r -x) # d
r*$_ # r*a(n-1)
($×=r) # r^n
+ * # r*a(n-1)+d*r^n
Z==$_ # Compare with each element of input
min # All elements are equal?
edited Nov 21 at 0:07
answered Nov 20 at 15:25
nwellnhof
6,3231125
6,3231125
add a comment |
add a comment |
up vote
2
down vote
JavaScript (ES7), 135 127 bytes
a=>!([x,y,z]=a,1/z)|!a.some(n=>n)|[y/x+(d=(y*y-x*z)**.5/x),y/x-d,z/y/2].some(r=>a.every((v,n)=>(v-(x+n*y/r-n*x)*r**n)**2<1e-9))
Try it online!
How?
We use two preliminary tests to get rid of some special cases. For the main case, we try three different possible values of $r$ (and the corresponding values of $d$, which can be easily deduced) and test whether all terms of the input sequence are matching the guessed ones. Because of potential rounding errors, we actually test whether all squared differences are $<10^{-9}$.
Special case #1: less than 3 terms
If there are less than 3 terms, it's always possible to find a matching sequence. So we force a truthy value.
Special case #2: only zeros
If all terms are equal to $0$, we can use $a_0=0$, $d=0$ and any $rneq 0$. So we force a truthy value.
Main case with $a_0=0$
If $a_0=0$, the sequence can be simplified to:
$$a_n=r^ntimes ntimes d$$
Which gives:
$$a_1=rtimes d\
a_2=2r^2times d$$
We know that $d$ is not equal to $0$ (otherwise, we'd be in the special case #2). So we have $a_1neq 0$ and:
$$r=frac{a_2}{2a_1}$$
Main case with $a_0neq 0$
We have the following relation between $a_{n+1}$ and $a_n$:
$$a_{n+1}=r.a_n+r^{n+1}d$$
For $a_{n+2}$, we have:
$$begin{align}a_{n+2}&=r.a_{n+1}+r^{n+2}d\
&=r(r.a_n+r^{n+1}d)+r^{n+2}d\
&=r^2a_n+2r.r^{n+1}d\
&=r^2a_n+2r(a_{n+1}-r.a_n)\
&=-r^2a_n+2r.a_{n+1}
end{align}$$
We notably have:
$$a_2=-r^2a_0+2r.a_1$$
Leading to the following quadratic:
$$r^2a_0-2r.a_1+a_2=0$$
Whose roots are:
$$r_0=frac{a_1+sqrt{{a_1}^2-a_0a_2}}{a_0}\
r_1=frac{a_1-sqrt{{a_1}^2-a_0a_2}}{a_0}$$
add a comment |
up vote
2
down vote
JavaScript (ES7), 135 127 bytes
a=>!([x,y,z]=a,1/z)|!a.some(n=>n)|[y/x+(d=(y*y-x*z)**.5/x),y/x-d,z/y/2].some(r=>a.every((v,n)=>(v-(x+n*y/r-n*x)*r**n)**2<1e-9))
Try it online!
How?
We use two preliminary tests to get rid of some special cases. For the main case, we try three different possible values of $r$ (and the corresponding values of $d$, which can be easily deduced) and test whether all terms of the input sequence are matching the guessed ones. Because of potential rounding errors, we actually test whether all squared differences are $<10^{-9}$.
Special case #1: less than 3 terms
If there are less than 3 terms, it's always possible to find a matching sequence. So we force a truthy value.
Special case #2: only zeros
If all terms are equal to $0$, we can use $a_0=0$, $d=0$ and any $rneq 0$. So we force a truthy value.
Main case with $a_0=0$
If $a_0=0$, the sequence can be simplified to:
$$a_n=r^ntimes ntimes d$$
Which gives:
$$a_1=rtimes d\
a_2=2r^2times d$$
We know that $d$ is not equal to $0$ (otherwise, we'd be in the special case #2). So we have $a_1neq 0$ and:
$$r=frac{a_2}{2a_1}$$
Main case with $a_0neq 0$
We have the following relation between $a_{n+1}$ and $a_n$:
$$a_{n+1}=r.a_n+r^{n+1}d$$
For $a_{n+2}$, we have:
$$begin{align}a_{n+2}&=r.a_{n+1}+r^{n+2}d\
&=r(r.a_n+r^{n+1}d)+r^{n+2}d\
&=r^2a_n+2r.r^{n+1}d\
&=r^2a_n+2r(a_{n+1}-r.a_n)\
&=-r^2a_n+2r.a_{n+1}
end{align}$$
We notably have:
$$a_2=-r^2a_0+2r.a_1$$
Leading to the following quadratic:
$$r^2a_0-2r.a_1+a_2=0$$
Whose roots are:
$$r_0=frac{a_1+sqrt{{a_1}^2-a_0a_2}}{a_0}\
r_1=frac{a_1-sqrt{{a_1}^2-a_0a_2}}{a_0}$$
add a comment |
up vote
2
down vote
up vote
2
down vote
JavaScript (ES7), 135 127 bytes
a=>!([x,y,z]=a,1/z)|!a.some(n=>n)|[y/x+(d=(y*y-x*z)**.5/x),y/x-d,z/y/2].some(r=>a.every((v,n)=>(v-(x+n*y/r-n*x)*r**n)**2<1e-9))
Try it online!
How?
We use two preliminary tests to get rid of some special cases. For the main case, we try three different possible values of $r$ (and the corresponding values of $d$, which can be easily deduced) and test whether all terms of the input sequence are matching the guessed ones. Because of potential rounding errors, we actually test whether all squared differences are $<10^{-9}$.
Special case #1: less than 3 terms
If there are less than 3 terms, it's always possible to find a matching sequence. So we force a truthy value.
Special case #2: only zeros
If all terms are equal to $0$, we can use $a_0=0$, $d=0$ and any $rneq 0$. So we force a truthy value.
Main case with $a_0=0$
If $a_0=0$, the sequence can be simplified to:
$$a_n=r^ntimes ntimes d$$
Which gives:
$$a_1=rtimes d\
a_2=2r^2times d$$
We know that $d$ is not equal to $0$ (otherwise, we'd be in the special case #2). So we have $a_1neq 0$ and:
$$r=frac{a_2}{2a_1}$$
Main case with $a_0neq 0$
We have the following relation between $a_{n+1}$ and $a_n$:
$$a_{n+1}=r.a_n+r^{n+1}d$$
For $a_{n+2}$, we have:
$$begin{align}a_{n+2}&=r.a_{n+1}+r^{n+2}d\
&=r(r.a_n+r^{n+1}d)+r^{n+2}d\
&=r^2a_n+2r.r^{n+1}d\
&=r^2a_n+2r(a_{n+1}-r.a_n)\
&=-r^2a_n+2r.a_{n+1}
end{align}$$
We notably have:
$$a_2=-r^2a_0+2r.a_1$$
Leading to the following quadratic:
$$r^2a_0-2r.a_1+a_2=0$$
Whose roots are:
$$r_0=frac{a_1+sqrt{{a_1}^2-a_0a_2}}{a_0}\
r_1=frac{a_1-sqrt{{a_1}^2-a_0a_2}}{a_0}$$
JavaScript (ES7), 135 127 bytes
a=>!([x,y,z]=a,1/z)|!a.some(n=>n)|[y/x+(d=(y*y-x*z)**.5/x),y/x-d,z/y/2].some(r=>a.every((v,n)=>(v-(x+n*y/r-n*x)*r**n)**2<1e-9))
Try it online!
How?
We use two preliminary tests to get rid of some special cases. For the main case, we try three different possible values of $r$ (and the corresponding values of $d$, which can be easily deduced) and test whether all terms of the input sequence are matching the guessed ones. Because of potential rounding errors, we actually test whether all squared differences are $<10^{-9}$.
Special case #1: less than 3 terms
If there are less than 3 terms, it's always possible to find a matching sequence. So we force a truthy value.
Special case #2: only zeros
If all terms are equal to $0$, we can use $a_0=0$, $d=0$ and any $rneq 0$. So we force a truthy value.
Main case with $a_0=0$
If $a_0=0$, the sequence can be simplified to:
$$a_n=r^ntimes ntimes d$$
Which gives:
$$a_1=rtimes d\
a_2=2r^2times d$$
We know that $d$ is not equal to $0$ (otherwise, we'd be in the special case #2). So we have $a_1neq 0$ and:
$$r=frac{a_2}{2a_1}$$
Main case with $a_0neq 0$
We have the following relation between $a_{n+1}$ and $a_n$:
$$a_{n+1}=r.a_n+r^{n+1}d$$
For $a_{n+2}$, we have:
$$begin{align}a_{n+2}&=r.a_{n+1}+r^{n+2}d\
&=r(r.a_n+r^{n+1}d)+r^{n+2}d\
&=r^2a_n+2r.r^{n+1}d\
&=r^2a_n+2r(a_{n+1}-r.a_n)\
&=-r^2a_n+2r.a_{n+1}
end{align}$$
We notably have:
$$a_2=-r^2a_0+2r.a_1$$
Leading to the following quadratic:
$$r^2a_0-2r.a_1+a_2=0$$
Whose roots are:
$$r_0=frac{a_1+sqrt{{a_1}^2-a_0a_2}}{a_0}\
r_1=frac{a_1-sqrt{{a_1}^2-a_0a_2}}{a_0}$$
edited Nov 21 at 12:06
answered Nov 20 at 15:58
Arnauld
70.7k688298
70.7k688298
add a comment |
add a comment |
up vote
2
down vote
Wolfram Language (Mathematica), 55 bytes
{}!=Solve[i=Range@Tr[1^#];(a+i*d)r^i==#,{r,a,d},Reals]&
Try it online!
Solve
return all solution forms. The result is compared with {}
to check if there is any solution.
add a comment |
up vote
2
down vote
Wolfram Language (Mathematica), 55 bytes
{}!=Solve[i=Range@Tr[1^#];(a+i*d)r^i==#,{r,a,d},Reals]&
Try it online!
Solve
return all solution forms. The result is compared with {}
to check if there is any solution.
add a comment |
up vote
2
down vote
up vote
2
down vote
Wolfram Language (Mathematica), 55 bytes
{}!=Solve[i=Range@Tr[1^#];(a+i*d)r^i==#,{r,a,d},Reals]&
Try it online!
Solve
return all solution forms. The result is compared with {}
to check if there is any solution.
Wolfram Language (Mathematica), 55 bytes
{}!=Solve[i=Range@Tr[1^#];(a+i*d)r^i==#,{r,a,d},Reals]&
Try it online!
Solve
return all solution forms. The result is compared with {}
to check if there is any solution.
edited Nov 24 at 14:33
answered Nov 20 at 14:43
user202729
13.6k12550
13.6k12550
add a comment |
add a comment |
If this is an answer to a challenge…
…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.
More generally…
…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f176262%2fis-it-an-arithmetico-geometric-sequence%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
FYI you can use inline math mode with
$
to write things like $ a_{0} $.– FryAmTheEggman
Nov 20 at 2:28
Are two-term inputs indeed possible? There aren't any in the test cases.
– xnor
Nov 20 at 3:40
@xnor Trivially you can set $r=1$ or $d=0$ so the sequences aren't unique in that case, but the output should always be truthy
– Giuseppe
Nov 20 at 3:55
1
Suggest testcase 0 2 8 24, 0 0 1, 0 0 0 1
– tsh
Nov 20 at 12:12
1
1 -1 0 4 16
would be a useful False case, since it shares four consecutive elements with each of the True cases1 -1 0 4 -16
and-1 -1 0 4 16
.– Anders Kaseorg
Nov 20 at 22:33