Sending data from arduino to phone

Hello everyone. I'm creating my own fitness tracker-esque device, which I hope to eventually connect to my android phone. I've worked with programs that send bluetooth data to the arduino, which is simple enough, but I have not worked on sending data to the android phone.I'm looking for very simple exchanges of data, such as syncing a clock to the tracker, and sending data (in the form of bytes, such as heart rate) to the phone.

My questions are, is this feasible, and how would I go about doing it?

Thank you for your help in advance.

muntasirms:
I've worked with programs that send bluetooth data to the arduino, which is simple enough,

Sending data from Arduino to Android is even simpler. I'm a fan of Bluetooth Graphics Terminal. BlueGraph is another but i have not yet used it.