Infer geometric sequences

Question

Haskell has this neat(-looking) feature where you can give it three numbers and it can infer an arithmetic sequence from them. For example, [1, 3..27] is equivalent to [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27].

That's cool and all but arithmetic sequences are fairly limiting. Addition, pfft. Multiplication's where it's at. Wouldn't it be cooler if it did geometric sequences like [1, 3..27] returning [1, 3, 9, 27]?

Challenge

Write a program/function that takes three positive integers a, b, and c and outputs [a, b, b × (b ÷ a), b × (b ÷ a)², ..., x] where x is the greatest integer ≤ c that can be represented as b × (b ÷ a)ⁿ where n is a positive integer.

That is, the output should be r, such that:

r₀ = a
r₁ = b
r_n = b × (b ÷ a)^n-1
r_last = greatest integer ≤ c that can be represented as b × (b ÷ a)ⁿ
         where n is a positive integer

Specifications

Standard I/O rules apply.
Standard loopholes are forbidden.
b will always be divisible by a.
a < b ≤ c
This challenge is not about finding the shortest approach in all languages, rather, it is about finding the shortest approach in each language.
Your code will be scored in bytes, usually in the encoding UTF-8, unless specified otherwise.
Built-in functions (Mathematica might have one :P) that compute this sequence are allowed but including a solution that doesn't rely on a built-in is encouraged.
Explanations, even for "practical" languages, are encouraged.

Test cases

a   b   c     r

1   2   11    [1, 2, 4, 8]
2   6   100   [2, 6, 18, 54]
3   12  57    [3, 12, 48]
4   20  253   [4, 20, 100]
5   25  625   [5, 25, 125, 625]
6   42  42    [6, 42]

In a few better formats:

Note that the formula is simply b^n/a^n-1. Starting at n=0 — H.PWiz, Feb 5, 2018 at 10:56
is it acceptable if the results are not exactly integers due to floating point errors? — Luis Mendo, Feb 6, 2018 at 22:56

Zgarb · Accepted Answer · 2018-02-05 13:30:44Z

Husk, 8 bytes

~↑≤Ṡ¡o//

Input is in order b, c, a. Try it online!

Explanation

~↑≤Ṡ¡o//  Implicit inputs.
       /  a/b as exact rational number.
     o/   Divide by a/b (so multiply by b/a).
    ¡     Iterate that function
   Ṡ      on a. Result is the infinite list [a, b, b^2/a, b^3/a^2, ..
 ↑        Take elements from it while
~ ≤       they are at most c.

The control flow in this program is a bit hard to follow. First, b is fed to the rightmost /, producing a function /b that divides by b. Next, ~ splits the remaining program into three parts: ~(↑)(≤)(Ṡ¡o//b). This feeds c to ≤ and a to Ṡ¡o//b, and combines the results with ↑. The result of ≤c is a function that checks if its argument is at most c, and ↑≤c takes the longest prefix of elements for which this holds.

It remains to show how (Ṡ¡o//b)a evaluates to the desired infinite list. The part in parentheses is split into Ṡ(¡)(o//b). Then Ṡ feeds a to o//b, feeds the result to ¡, and then gives a to its second argument. The expression (o//b)a gives a function that takes a number and divides it by a/b, and ¡ iterates this function on its second argument, which is a.

Here is a series of transformations that visualize the explanation:

  (~↑≤Ṡ¡o//) b c a
= (~↑≤Ṡ¡o/(/b)) c a
= ~(↑)(≤)(Ṡ¡o/(/b)) c a
= ↑(≤c)((Ṡ¡o/(/b)) a)
= ↑(≤c)(Ṡ(¡)(o/(/b)) a)
= ↑(≤c)(¡(o/(/b)a) a)
= ↑(≤c)(¡(/(/ba))a)
Last line in English: takeWhile (atMost c) (iterate (divideBy (divideBy b a)) a)

Alternative solution using explicit variables in order a, b, c:

↑≤⁰¡*/⁵²

Community · Accepted Answer · 2020-06-17 09:04:33Z

5

Python 2, 42 bytes

a,b,c=input()
x=b/a
while c/a:print a;a*=x

Try it online!

Recursive approach, 42 41 bytes

^{-1 byte thanks to ovs}

f=lambda a,b,c:c/a*[a]and[a]+f(b,b*b/a,c)

Try it online!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Feb 5, 2018 at 11:30

Rod

18.4k4 gold badges30 silver badges89 bronze badges

Add a comment |

Mr. Xcoder · Accepted Answer · 2018-02-05 12:35:33Z

4

Proton, 35 bytes

f=(a,b,c)=>c//a?[a]+f(b,b*b/a,c):[]

Try it online!

answered Feb 5, 2018 at 12:35

Mr. Xcoder

42.4k9 gold badges79 silver badges214 bronze badges

1

\$\begingroup\$ people actually remember this language? :D \$\endgroup\$
– hyper-neutrino ♦
Feb 5, 2018 at 13:13
1

\$\begingroup\$ @HyperNeutrino I actively use it :) \$\endgroup\$
– Mr. Xcoder
Feb 5, 2018 at 13:16
3

\$\begingroup\$ I know that I am probably not going to receive any answer, but why the downvote? \$\endgroup\$
– Mr. Xcoder
Feb 5, 2018 at 18:18

Add a comment |

alephalpha · Accepted Answer · 2018-02-05 11:16:43Z

3

Wolfram Language (Mathematica), 22 bytes

PowerRange[#,#3,#2/#]&

Try it online!

answered Feb 5, 2018 at 11:16

alephalpha

48k7 gold badges62 silver badges175 bronze badges

Add a comment |

Arnauld · Accepted Answer · 2018-02-05 15:10:32Z

JavaScript (ES6), 41 37 bytes

Saved 4 bytes thanks to @Neil

Takes input as (b,c)(a).

(b,c)=>g=a=>a>c?[]:[a,...g(b,b*=b/a)]

Test cases

let f =

(b,c)=>g=a=>a>c?[]:[a,...g(b,b*=b/a)]

console.log(JSON.stringify(f(2,11)(1)))
console.log(JSON.stringify(f(6,100)(2)))
console.log(JSON.stringify(f(12,57)(3)))
console.log(JSON.stringify(f(20,253)(4)))
console.log(JSON.stringify(f(42,42)(6)))

Commented

(b, c) =>                 // main function taking b and c
  g = a =>                // g = recursive function taking a
    a > c ?               //   if a is greater than c:
      []                  //     stop recursion and return an empty array
    :                     //   else:
      [ a,                //     return an array consisting of a, followed by 
        ...g(             //     the expanded result of a recursive call to g()
          b,              //       with a = b
          b *= b / a      //       and b = b * ratio
        ) ]               //     end of recursive call

Rearranging the arguments gives me (b,c)=>g=a=>a>c?[]:[a,...g(b,b*=b/a)]. — Neil, Feb 5, 2018 at 13:45

alephalpha · Accepted Answer · 2018-02-15 17:57:42Z

3

Pari/GP, 38 bytes

f(a,b,c)=powers(b/a,logint(c\a,b/a),a)

Try it online!

edited Feb 15, 2018 at 17:57

answered Feb 5, 2018 at 11:30

alephalpha

48k7 gold badges62 silver badges175 bronze badges

Add a comment |

Manish Kundu · Accepted Answer · 2018-02-05 15:03:19Z

2

Python 3, 93 90 74 73 bytes

x=lambda a,b,c,i=0,q=[]:a*(b/a)**i>c and q or x(a,b,c,i+1,q+[a*(b/a)**i])

Try It Online

Thanks to Rod and user202729 for helping me reduce quite some bytes!

edited Feb 5, 2018 at 15:03

answered Feb 5, 2018 at 10:51

Manish Kundu

5,2702 gold badges15 silver badges47 bronze badges

1

\$\begingroup\$ def + return -> lambda. Python tips. \$\endgroup\$
– DELETE_ME
Feb 5, 2018 at 10:53
1

\$\begingroup\$ Also you can import*. \$\endgroup\$
– DELETE_ME
Feb 5, 2018 at 10:53
1

\$\begingroup\$ you can use while i<=c:i++ (instead list comprehension+log) to save a lot of bytes \$\endgroup\$
– Rod
Feb 5, 2018 at 10:54
\$\begingroup\$ @Rod How should I use the while loop without the log? idk how long to iterate \$\endgroup\$
– Manish Kundu
Feb 5, 2018 at 11:01
1

\$\begingroup\$ -1 byte. \$\endgroup\$
– DELETE_ME
Feb 5, 2018 at 12:26

| Show 2 more comments

Sanchises · Accepted Answer · 2018-02-07 13:54:06Z

2

Octave, 38 35 bytes

@(a,b,c)exp(log(a):log(b/a):log(c))

Try it online!

Turns out @LuisMendo's MATL approach also saves 3 bytes in Octave, despite repeating log three times.

edited Feb 7, 2018 at 13:54

answered Feb 5, 2018 at 11:07

Sanchises

9,4961 gold badge35 silver badges61 bronze badges

Add a comment |

Sean · Accepted Answer · 2018-02-17 05:10:12Z

2

Perl 6, 26 24 bytes

{$^a,$^b,$b²/$a...^*>$^c}
{$^a,*×$^b/$a...^*>$^c}

Try it online!

Perl 6's sequence operator ... can infer geometric series natively.

Update: ...It can, but in this situation not inferring it is a bit shorter.

edited Feb 17, 2018 at 5:10

answered Feb 16, 2018 at 21:35

Sean

7,92610 silver badges15 bronze badges

Add a comment |

Emigna · Accepted Answer · 2018-02-05 11:26:32Z

1

05AB1E, 12 bytes

Input in the order c,b,a

ÝmI¹Ý<m/ʒ¹›_

Try it online!

Explanation

Ý              # push the range [0 ... c]
 m             # raise b to the power of each
  I            # push a
   ¹Ý          # push the range [0 ... c]
     <         # decrement each
      m        # push a to the power of each
       /       # elementwise division of ranges
        ʒ      # filter, keep only elements that are
         ¹›_   # not greater than c

edited Feb 5, 2018 at 11:26

answered Feb 5, 2018 at 11:15

Emigna

53k5 gold badges42 silver badges162 bronze badges

Add a comment |

Sanchises · Accepted Answer · 2018-02-05 11:43:29Z

1

MATL, 17 bytes

t:,qtiw^w]x/tb>~)

Try it online!

Just to get the ball rolling in MATL. I can't imagine there isn't a less verbose way of solving this.

answered Feb 5, 2018 at 11:43

Sanchises

9,4961 gold badge35 silver badges61 bronze badges

1

\$\begingroup\$ ... No triple negation please. \$\endgroup\$
– DELETE_ME
Feb 5, 2018 at 12:34
2

\$\begingroup\$ @user202729 I don't see how you could not have gotten that that wasn't an accident.:) \$\endgroup\$
– Sanchises
Feb 5, 2018 at 12:47
\$\begingroup\$ Don't you mean "I don't see how you could not have gotten that that wasn't done unintentionally" :P \$\endgroup\$
– hyper-neutrino ♦
Feb 5, 2018 at 14:11
\$\begingroup\$ @HyperNeutrino No. \$\endgroup\$
– Sanchises
Feb 5, 2018 at 15:32
\$\begingroup\$ Keep the ball rolling \$\endgroup\$
– Luis Mendo
Feb 6, 2018 at 22:57

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Haskell, 35 bytes

(a#b)c|a>c=[]|d<-div b a*b=a:(b#d)c

Try it online!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Feb 5, 2018 at 15:36

nimi

35.8k4 gold badges34 silver badges96 bronze badges

1

\$\begingroup\$ 34 bytes. (more "in the spirit of the challenge", terrible floating point error) \$\endgroup\$
– DELETE_ME
Feb 5, 2018 at 15:58
\$\begingroup\$ @user202729: please post it as a separate answer (but save a byte: exp<$>[...]) \$\endgroup\$
– nimi
Feb 5, 2018 at 17:13

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

MATL, 12 bytes

y/ivZlZ}3$:W

Try it online! Or verify all test cases.

Explanation

y     % Implicitly take two inputs, and duplicate the first onto the top
/     % Divide
i     % Take third input
v     % Vertically concatenate the three numbers into a column vector
Zl    % Binary logarithm, element-wise
Z}    % Split the vector into its three components
3$:   % Three-input range. Arguments are start, step, upper limit
W     % 2 raised to that, element-wise. Implicit display

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Feb 6, 2018 at 22:57

Luis Mendo

104k9 gold badges133 silver badges370 bronze badges

1

\$\begingroup\$ This is really nice. I was struggling with reusing a and c (I have many failed attempts starting with y/i), but using this method, you neatly keep everything together. \$\endgroup\$
– Sanchises
Feb 7, 2018 at 7:18
1

\$\begingroup\$ this approach was actually 3 bytes shorter in Octave too. \$\endgroup\$
– Sanchises
Feb 7, 2018 at 13:54

Add a comment |

Ton Hospel · Accepted Answer · 2018-02-05 12:50:51Z

0

Perl, 38 bytes

Include +3 for -n (the use 5.10.0 to unlock the perl 5.10 features is free)

#!/usr/bin/perl -n
use 5.10.0;
/ \d+/;say,$_*=$&/$`until($_+=0)>$'

Then run as:

geosequence.pl <<< "1 3 26"

answered Feb 5, 2018 at 12:50

Ton Hospel

14.9k1 gold badge22 silver badges45 bronze badges

Add a comment |

Galen Ivanov · Accepted Answer · 2018-02-05 13:46:41Z

0

Red, 50 bytes

g: func[a b c][if a <= c[print a g b b * b / a c]]

Try it online!

answered Feb 5, 2018 at 13:46

Galen Ivanov

21k3 gold badges23 silver badges61 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Japt, 14 bytes

ÆWpX zVpXÉÃf§U

Try it

Explanation

                    :Implicit input of integers U=c, V=a & W=b
Æ         Ã         :Range [0,U) and pass each X through a function
 WpX                :  W to the power of X
     z              :  Floor divide by
      VpXÉ          :  V to the power of X-1
           f§U      :Filter elements less than or equal to U

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Feb 5, 2018 at 14:45

Shaggy

41.9k4 gold badges34 silver badges93 bronze badges

Add a comment |

Οurous · Accepted Answer · 2018-02-05 22:47:25Z

0

Clean, 63 bytes

import StdEnv
$a b c=takeWhile((>=)c)[a:map(\n=b*b^n/a^n)[0..]]

Try it online!

answered Feb 5, 2018 at 22:47

Οurous

8,1071 gold badge16 silver badges38 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

TI-BASIC, 31 bytes

Takes input from user and outputs in Ans. I solved for n in c = bⁿ / a^n-1, getting n = 1 + ln(c/b) / ln(b/a). That's the same as n = 1 + log_b/a(c/b). For the purposes of golfing, I start my sequence at -1 and end it at n-1 rather than 0 to n.

Prompt A,B,C
seq(B(B/A)^N,N,-1,logBASE(C/B,B/A

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Feb 5, 2018 at 23:53

kamoroso94

7995 silver badges9 bronze badges

Add a comment |

J. Sallé · Accepted Answer · 2018-02-16 15:08:45Z

APL (Dyalog Unicode), 38 bytes

{(g≤⊃⌽⍵)⊆g←f,(⍵[1]*p+1)÷(f←⊃⍵)*p←⍳⊃⌽⍵}

Try it online!

Prefix Dfn. Takes input in order a b c, and uses ⎕IO←0 (Index Origin)

Thanks to @ErikTheOutgolfer for shaving 6 bytes out of this before I even posted it.

How?

{(g≤⊃⌽⍵)⊆g←f,(⍵[1]*p+1)÷(f←⊃⍵)*p←⍳⊃⌽⍵} ⍝ Prefix Dfn. Input ⍵ is a vector
                                    ⌽⍵  ⍝ Reverse ⍵. Yields c b a
                                   ⊃    ⍝ Pick the first element (c)
                                  ⍳     ⍝ Index. Yields the integers 0..c-1
                                p←      ⍝ Assign to the variable p
                               *        ⍝ Exponentiate
                         (f←⊃⍵)         ⍝ Pick the first element of ⍵ (a) and assign to f
                                        ⍝ This yields the vector (a^0, a^1, ..., a^c-1)
                        ÷               ⍝ Element-wise division
                    p+1)                ⍝ The vector 1..c
                   *                    ⍝ Exponentiate
              (⍵[1]                     ⍝ Second element (because of ⎕IO←0) of ⍵ (b)
                                        ⍝ This yields the vector (b^1, b^2, ..., b^c)
            f,                          ⍝ Prepend f (a). This yields the vector 
                                        ⍝ (a, b^1/a^0, b^2/a^1, ...)
          g←                            ⍝ Assign the vector to g
         ⊆                              ⍝ Partition. This takes a boolean vector as left
                                        ⍝ argument and drops falsy elements of the right argument.
     ⊃⌽⍵)                               ⍝ Pick the last element of ⍵ (c)
  (g≤                                   ⍝ Check if each element of g≤c. Yields the boolean
                                        ⍝ vector that is the left argument for ⊆

Community · Accepted Answer · 2020-06-17 09:04:33Z

Stax, 14 bytes^CP437

ü╞¥ß¥║/,5å╘⌂åº

16 bytes when unpacked,

E~Y/y{;^<}{[*gfm

Run and debug online!

Takes input in the form of [b, a, c].

Pretty sure @recursive has better solutions.

Explanation

E~                              Parse  input, put `c` on input stack
  Y/                            Store `a` in register `y` and calculate `b`/`a`
    y                           Put `y` back to main stack, stack now (from top to bottom): [`a`, `b`/`a`]
     {   }{  gf                 generator
      ;^<                       Condition: if the generated number is smaller than the top of input stack (i.e. `c`)
           [*                   duplicate the second item in main stack and multiply it with the item at the top
                                   i.e. multiply last generated value by `b/a` and generate the value
              m                 Output array, one element on each line

Rohan Jhunjhunwala · Accepted Answer · 2018-02-16 16:35:46Z

0

S.I.L.O.S, 73 bytes

readIO
k=i
readIO
j=i
readIO
r=j/k
a=k
lbla
printInt a
a*r
b=i-a+1
if b a

Try it online!

We read the three numbers. Calculate the common ratio by the second number/ first one. Then we run through the series until we are greater than the upper bound.

answered Feb 16, 2018 at 16:35

Rohan Jhunjhunwala

2,66617 silver badges39 bronze badges

Add a comment |

vazt · Accepted Answer · 2018-02-16 21:23:44Z

0

C (gcc), 82 bytes

n;f(a,b,c){float r=0;for(n=0;r<=c;)(r=pow(b,n)/pow(a,n++-1))<=c&&printf("%f ",r);}

Try it online!

Calculates and prints r_n = b^n/a^(n-1) until r_n > c.

Must be compiled with -lm!

answered Feb 16, 2018 at 21:23

vazt

3111 silver badge4 bronze badges

\$\begingroup\$ 69 bytes n;f(a,b,c){for(float r=n=0;r=pow(b/a,n++)*a,r<=c&&printf("%f ",r););} \$\endgroup\$
– ceilingcat
Aug 6, 2018 at 22:16

Add a comment |

H.PWiz · Accepted Answer · 2018-02-16 21:25:01Z

APL (Dyalog), 23 bytes (SBCS)

This takes arguments a b on the left and c on the right,

{⊃(⍵∘≥⊆⊢)⊣/⍵2⍴⍺,÷\⍵⍴⌽⍺}

Try it online!

There is likely a shorter way, but I thought that ÷\ was cute.

Explained:

{...} Anonomous function ⍺ is a b, ⍵ is c. Lets say a b c = 2 6 100

⌽⍺ Reverse ⍺: 6 2

⍵⍴ Repeat ⍵ times: 6 2 6 2 6 2 6 2 ...

÷\ Reduce by division on prefixes: 6 (6÷2) (6÷(2÷6)) (6÷(2÷(6÷2))).. = 6 3 18 9 54 ..

⍺, Prepend ⍺: 2 6 6 3 18 9 54 27 162 81 ...

⊣/⍵2⍴ Get every other element (plus some trailing repeats):

⍵2⍴ Make an ⍵ row, 2 column matrix from 2 6 6 3 18 9 54 ...

⊣/ Get the first column

⊆⊢ Split the array into blocks where

⍵∘≥ ⍵ is greater than or equal to all the elements

⊃ Take the first such block

Infer geometric sequences

Challenge

Specifications

Test cases

23 Answers 23

Husk, 8 bytes

Explanation

Python 2, 42 bytes

Recursive approach, 42 41 bytes

Proton, 35 bytes

Wolfram Language (Mathematica), 22 bytes

JavaScript (ES6), 41 37 bytes

Test cases

Commented

Pari/GP, 38 bytes

Python 3, 93 90 74 73 bytes

Octave, 38 35 bytes

Perl 6, 26 24 bytes

05AB1E, 12 bytes

MATL, 17 bytes

Haskell, 35 bytes

MATL, 12 bytes

Explanation

Perl, 38 bytes

Red, 50 bytes

Japt, 14 bytes

Explanation

Clean, 63 bytes

TI-BASIC, 31 bytes

APL (Dyalog Unicode), 38 bytes

How?

Stax, 14 bytesCP437

Explanation

S.I.L.O.S, 73 bytes

C (gcc), 82 bytes

APL (Dyalog), 23 bytes (SBCS)

Explained:

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfmathnumbersequence or ask your own question.

Linked

Related

Hot Network Questions

Stax, 14 bytes^CP437

Not the answer you're looking for? Browse other questions tagged
code-golf
math
number
sequence
or ask your own question.