18
\$\begingroup\$

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)2, ..., x] where x is the greatest integer ≤ c that can be represented as b × (b ÷ a)n where n is a positive integer.

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

r0 = a
r1 = b
rn = b × (b ÷ a)n-1
rlast = greatest integer ≤ c that can be represented as b × (b ÷ a)n
         where n is a positive integer

Specifications

  • Standard I/O rules apply.
  • Standard loopholes are forbidden.
  • b will always be divisible by a.
  • a < bc
  • 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:

1 2 11
2 6 100
3 12 57
4 20 253
5 25 625
6 42 42

1, 2, 11
2, 6, 100
3, 12, 57
4, 20, 253
5, 25, 625
6, 42, 42
\$\endgroup\$
  • \$\begingroup\$ @Adám No. (see the first test case) \$\endgroup\$ – user202729 Feb 5 '18 at 10:46
  • 1
    \$\begingroup\$ Note that the formula is simply b^n/a^n-1. Starting at n=0 \$\endgroup\$ – H.PWiz Feb 5 '18 at 10:56
  • 2
    \$\begingroup\$ Of course Mathematica has a built-in... \$\endgroup\$ – Neil Feb 5 '18 at 13:47
  • \$\begingroup\$ is it acceptable if the results are not exactly integers due to floating point errors? \$\endgroup\$ – Luis Mendo Feb 6 '18 at 22:56
  • \$\begingroup\$ @LuisMendo Yes. \$\endgroup\$ – totallyhuman Feb 6 '18 at 22:57

23 Answers 23

6
\$\begingroup\$

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:

↑≤⁰¡*/⁵²
\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

Proton, 35 bytes

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ people actually remember this language? :D \$\endgroup\$ – HyperNeutrino Feb 5 '18 at 13:13
  • 1
    \$\begingroup\$ @HyperNeutrino I actively use it :) \$\endgroup\$ – Mr. Xcoder Feb 5 '18 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 '18 at 18:18
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Rearranging the arguments gives me (b,c)=>g=a=>a>c?[]:[a,...g(b,b*=b/a)]. \$\endgroup\$ – Neil Feb 5 '18 at 13:45
3
\$\begingroup\$

Pari/GP, 38 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 22 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ def + return -> lambda. Python tips. \$\endgroup\$ – user202729 Feb 5 '18 at 10:53
  • 1
    \$\begingroup\$ Also you can import*. \$\endgroup\$ – user202729 Feb 5 '18 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 '18 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 '18 at 11:01
  • 1
    \$\begingroup\$ -1 byte. \$\endgroup\$ – user202729 Feb 5 '18 at 12:26
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ ... No triple negation please. \$\endgroup\$ – user202729 Feb 5 '18 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 '18 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\$ – HyperNeutrino Feb 5 '18 at 14:11
  • \$\begingroup\$ @HyperNeutrino No. \$\endgroup\$ – Sanchises Feb 5 '18 at 15:32
  • \$\begingroup\$ Keep the ball rolling \$\endgroup\$ – Luis Mendo Feb 6 '18 at 22:57
1
\$\begingroup\$

Haskell, 35 bytes

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

Try it online!

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

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
\$\endgroup\$
  • 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 '18 at 7:18
  • 1
    \$\begingroup\$ this approach was actually 3 bytes shorter in Octave too. \$\endgroup\$ – Sanchises Feb 7 '18 at 13:54
0
\$\begingroup\$

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"
\$\endgroup\$
0
\$\begingroup\$

Red, 50 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

Clean, 63 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

TI-BASIC, 31 bytes

Takes input from user and outputs in Ans. I solved for n in c = bn / an-1, getting n = 1 + ln(c/b) / ln(b/a). That's the same as n = 1 + logb/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
\$\endgroup\$
0
\$\begingroup\$

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 ⊆
\$\endgroup\$
0
\$\begingroup\$

Stax, 14 bytesCP437

ü╞¥ß¥║/,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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
  • \$\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 '18 at 22:16
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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