# Draw a phi triangle

Clarification: Basically, you need to make this

Euler's totient function has the name phi.

Let's try to calculate phi(8)

First, list all numbers 8 and under backwards, not including 0 or under

8
7
6
5
4
3
2
1


Now find which numbers don't share a factor with 8 (1 doesn't count), and place a # in their place.

8
#
6
#
4
#
2
#


Remove the numbers.

#

#

#

#
-


Now do this, but string the outputs together in a triangle

        9
88
777
6666
55555
444444
3333333
22222222
111111111
---------
123456789


# out non-factor sharing numbers

        9
8#
7##
6#66
5####
4#4#4#
3##3##3
2#2#2#2#
#########


Remove numbers:

        #
##
#
####
# # #
## ##
# # # #
#########


This would be the output for input 9 (since 9 columns.)

• Clarification needed.
– user53397
May 1, 2016 at 23:29
• if you need to clarify, try the sandbox first. May 1, 2016 at 23:35
• can I output as a list of lines? May 2, 2016 at 0:52
• Leading newline allowed? May 2, 2016 at 1:25

# MATL, 17 15 bytes

:Gq:!Zd1=RP35*c


Try it online!

If a leading newline is acceptable: 13 bytes:

:t!Zd1=RP35*c


### Explanation

:     % Take input N. Generate row vector [1 2 ... N]
Gq:   % Row vector [1 2 ... N-1].
% (In the 13-byte version this is replaced by function t, which duplicates
% the array [1 2 ... N])
!     % Transpose into column vector
Zd    % GCD, element-wise with broadcast. Gives (N-1)×N matrix
1=    % True for entries that equal 1, corresponding to relatively prime pairs.
% The rest of entries are set to false, i.e. 0.
R     % Upper triangular part: set values below diagonal to 0
P     % Flip matrix vertically
35*   % Multiply each entry by 35 (ASCII for '#')
c     % Convert to char. 0 will be displayed as a space. Implicitly display

• Nice use of char(0) :) May 2, 2016 at 12:54
• @Suever It's turning out to be very useful! May 2, 2016 at 14:23

# Jelly, 20 18 bytes

RR⁶”#g’¥?€"Rz⁶U'j⁷


Try it online!

# Pyth - 22 bytes

Will try to golf further.

j_.tmsm@"# "n1idkSdSQd

• I did it in 20 bytes. May 2, 2016 at 0:44
• Well.... 21 bytes. May 2, 2016 at 0:49

## JavaScript (ES6), 112 bytes

n=>[...s= .repeat(n)].map(_=>s.replace(/./g,_=># [+g(n+1,i++)],n-=i=1),g=(i,j)=>i?i>j||g(j%i,i):j>1).join\n


Where \n represents the literal newline character. Alternative solution, also 112 bytes:

n=>(s=# .repeat(n)).replace(r=/../g,_=>s.replace(r,m=>m[+g(n+1,i++)],n-=i=1)+
,g=(i,j)=>i?i>j||g(j%i,i):j>1)


# Java, 162 158 bytes

int g(int a,int b){return a<1?b:g(b%a,a);}
String d(int n){String r="";for(int i=0;i<n;i++){for(int j=1;j<=n;)r+=i+j<n|g(n-i,j++)>1?" ":"#";r+="\n";}return r;}


Full program (not updated)

import java.util.Scanner;

public class Q79082 {
int gcd_ungolfed(int a,int b){
if(a==0) return b;
return gcd_ungolfed(b%a,a);
}
void draw_ungolfed(int n){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i+j<=n || gcd_ungolfed(n+1-i,j)!=1){
System.out.print(" ");
}else{
System.out.print("#");
}
}
System.out.println();
}
}
int g(int a,int b){return a<1?b:g(b%a,a);}
String d(int n){String r="";for(int i=0;i<n;i++){for(int j=1;j<=n;j++)r+=(i+j<n||g(n-i,j)>1)?" ":"#";r+="\n";}return r;}
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.close();
new Q79082().draw_ungolfed(n);
System.out.println(new Q79082().d(n));
}
}


Input/output:

9

#
##
#
####
# # #
## ##
# # # #
#########

#
##
#
####
# # #
## ##
# # # #
#########

• Make the shortcutted or into a single pipe, then put i++ and j++ in the call to g. Will save 3 bytes. Also, you don't need the parens in the trinary in d. 2 more bytes
– Blue
May 2, 2016 at 1:24
• i++ won't work because nested. May 2, 2016 at 1:42

# SQL (PostGreSQL9.4), 239 291 bytes

Creates a prepared statement that can be executed. I'm sure I can probably take quite a few bytes out of this, but I'll have to pick away at it later. Does a cross join on a range of 1 to n. Calculates the GCD in a lateral join. Where the GCD is 1 and the series A is greater than series B output a '#' otherwise a space. Aggregate the results up into a string grouped by series B.

prepare p(int)as
select string_agg(coalesce(CASE WHEN b<=a AND x=1THEN'#'END,' '),'')from generate_series(1,$1)a,generate_series(1,$1)b,LATERAL(SELECT MAX(G)x FROM generate_series(1,LEAST(a,b))g WHERE a%g+b%g=0)g
group by b
order by b desc


Run in the following way

execute p(13)

string_agg
----------------

#
##
# #
## #
# # #
######
#   # #
#### ###
# # # # #
## ## ## #
# # # # # #
#############


And cleaned up with

deallocate p


# Ruby, 84 bytes

->n{s=[];n.times{|i|j=0;m=n-i;s<<(?#*n).gsub(/./){m.gcd(j+=1)>1||m>j ?' ':$&}};s*$/}


## Python 2 (120 bytes)

g=lambda m,n:m if n<1 else g(n,m%n)
r=range(input())
for i in r[:0:-1]:print''.join('# '[i>j+1 or g(i,j+1)>1]for j in r)